Recursive inorder traversal of a binary search tree

Question

I want to implement a recursive inorder in a binary search tree (BST). I built a tree using two structs: Node and Tree. My code has not worked so far, mainly because of a type mismatch in Node::inorder.

pub struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

pub struct Tree<T> {
    root: Option<Box<Node<T>>>,
}

impl<T: Ord> Tree<T> {
    /// Creates an empty tree
    pub fn new() -> Self {
        Tree { root: None }
    }

    pub fn inorder(&self) -> Vec<&T> {
        self.root.as_ref().map(|n| n.inorder()).unwrap() // how to pass result ?
    }
}

impl<T: Ord> Node<T> {
    pub fn inorder(&self) -> Vec<&T> {
        let mut result: Vec<&T> = Vec::new();

        match *self {
            None => return result,

            Some(ref node) => {
                let left_vec = node.left.inorder();
                result.extend(left_vec);
                result.extend(node.value);
                let right_vec = node.right.inorder();
                result.extend(right_vec);
            }
        }
    }
}

This is the error report:

error[E0308]: mismatched types
  --> src/main.rs:27:13
   |
27 |             None => return result,
   |             ^^^^ expected struct `Node`, found enum `std::option::Option`
   |
   = note: expected type `Node<T>`
   = note:    found type `std::option::Option<_>`

error[E0308]: mismatched types
  --> src/main.rs:29:13
   |
29 |             Some(ref node) => {
   |             ^^^^^^^^^^^^^^ expected struct `Node`, found enum `std::option::Option`
   |
   = note: expected type `Node<T>`
   = note:    found type `std::option::Option<_>`

In Node::inorder, I want to return a empty vector if a node does not exist; if the node does exist, I want to grow the vector inorder and recur. The match doesn't work between a Node and Option, but I am not sure how to bridge between them.

You should upgrade your version of Rust to get the improved error messages. I've edited this question with them as they are also easier to read. — Shepmaster, Dec 03 '16 at 15:01

score 4 · Answer 1 · edited May 23 '17 at 12:13

Chris Emerson's answer is correct, but I'd advocate for a more memory efficient version that always appends to the same vector. This prevents excessive copying of the values.

impl<T> Tree<T> {
    pub fn inorder(&self) -> Vec<&T> {
        let mut nodes = Vec::new();
        if let Some(ref root) = self.root {
            root.inorder(&mut nodes);
        }
        nodes
    }
}

impl<T: Ord> Node<T> {
    pub fn inorder<'a>(&'a self, result: &mut Vec<&'a T>) {
        if let Some(ref left) = self.left {
            left.inorder(result);
        }
        result.push(&self.value);
        if let Some(ref right) = self.right {
            right.inorder(result);
        }
    }
}

Note that I've removed the : Ord restriction as it's not needed for traversal.

Even better would be to create an iterator that traverses inorder, then you could just call collect.

score 3 · Accepted Answer · answered Dec 03 '16 at 08:29

The problem is that there's confusion about where the options are:

impl<T: Ord> Node<T> {
    pub fn inorder(&self) -> Vec<&T> {
    //...
    match *self {

Here, self is a Node<T>, not an option. Instead, self.left and self.right are options.

This compiles (until lack of main()):

pub fn inorder(&self) -> Vec<&T> {

    let mut result: Vec<&T> = Vec::new();

    if let Some(ref left) = self.left {
        let left_vec = left.inorder();
        result.extend(left_vec);
    }
    result.push(&self.value);
    if let Some(ref right) = self.right {
        let right_vec = right.inorder();
        result.extend(right_vec);
    }
    result
}

I also added the return, and fixed result.extend(self.value) to instead push a reference.

Playground

Recursive inorder traversal of a binary search tree

2 Answers2

Linked