How to implement searching a given key in Bianry Search Tree?

struct Node {
  value: Option<i32>, // data feild
  left: Option<Box<Node>>, // left child
  right: Option<Box<Node>>, // right child
}

impl Node {
  // search for a Node with key, and return the value or None
  // root_Node {
  // value: None,
  // left: None,
  // right: None,
  // }
  pub fn search(&self, x: Option<i32>) -> Option<i32> {
    if self.left == None && self.right == None && self.value == None {
      return None;
    } else {
      if x < self.value {
        return self.left.search(x); // Error: No method search for std::option::Option<std::boxed::Box<Node>
    } else if x > self.value {
        return self.right.search(x); // Error: Same as above
    } else {
        return self.value;
    }
  }
}

I am reimplementing my DataStructure learning codes with Rust, this piece of code is for searching in a binary tree. I am new to Rust, not familiar with Rust syntax, Could you give a hint to me to unwrap it ?
The origin Option::unwrap() method leads to borrow error (self.left.unwrap().search(key))

Regarding this:

value: Option<i32>, // data feild

Are you sure you don't want just a i32 key?

value: i32, // data feild

You need:

if let Some(ref left) = self.left { left.search(…) }

== None does not unwrap, so you still need to convert Option<Node> to Node. You could use self.left.unwrap() after checking == None, but that is more error prone than if let.

(fixed ref)

Isn't that going to try moving the Box out of the Option? Instead, it should probably be "let Some(ref left) = ...". Alternatively, can probably use things like "self.left.as_ref().map(...)" to recurse into the subtrees without moving anything out.

1 Like

Firstly, @impltrait, I don't quite understand your types and signatures. As with @leonardo, I expected a straight up i32 in there instead of an Option<i32>. So I'm going to change the signatures around a lot and write an implementation that more closely resembles Java or C++ where you would pass in a nullable tree Node and use it's nullness as the stopping condition on a failed search. In Rust, the equivalent of a nullable Node pointer is an Option<&Node>, so we'll write a helper function that works on that.

Since you said you're new, I added a bunch of comments to help explain what's going on.

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

pub fn search(opt_node: Option<&Node>, x: i32) -> Option<&Node> {
  // Using `and_then()` instead of `map()` to avoid ending up
  // with `Option<Option<&Node>>`.
  // Both methods return `None` if `opt_node` is `None`.
  opt_node.and_then(|node| {
    if x < node.value {
      // The first parameter undergoes these type transitions:
      //   Option<Box<Node>>   (node.left)
      //   --as_ref--> Option<&Box<Node>>
      //   --map--> Option<&Node>
      search(node.left.as_ref().map(|bx| bx.as_ref()), x)
    } else if x > node.value {
      search(node.right.as_ref().map(|bx| bx.as_ref()), x)
    } else {
      Some(node)
    }
  })
}

impl Node {
  // Returns the `Node`, if any, where the i32 was found.
  // There's no point returning the i32 itself. If you
  // just want to indicate that a node was found, just return
  // a `bool` and rename this method to `contains` instead.
  pub fn search(&self, x: i32) -> Option<&Node> {
    search(Some(self), x)
  }
}

Playground link

@vitalyd
@kornel
Thank you, I have done it with your tips.


@marcianx
@leonardo
I wrote value: Option<i32>, because I didn't know how to set the root to be None (without value, left and right). With value: Option<i32>, the value field can be set to None, that's the reason I do this.
@marcianx Thank for you great explaination, it helps me a lot.

Here's how I'd do it with more pattern matching while keeping the value to be optional:

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

impl Node {
    pub fn search(&self, x: i32) -> Option<i32> {
        use std::cmp::Ordering::*;
        if let Some(value) = self.value {
            match (x.cmp(&value), &self.left, &self.right) {
                (Less, &Some(ref left), _) => left.search(x),
                (Greater, _, &Some(ref right)) => right.search(x),
                (Equal, _, _) => Some(x),
                _ => None,
            }
        } else {
            None
        }
    }
}
1 Like

For this problem you could use a wrapping struct, like

struct BinSearchTree {
        root: Option<Node>
        // you could also save other info, like the number of nodes, for fast retrieve
}
1 Like

+1. This also makes it impossible to have incorrect state in the tree like a node having no value but having a left or right child with values.

My code from above with value: i32:

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

impl Node {
    pub fn search(&self, x: i32) -> Option<i32> {
        use std::cmp::Ordering::*;
        match (x.cmp(&self.value), &self.left, &self.right) {
            (Less, &Some(ref left), _) => left.search(x),
            (Greater, _, &Some(ref right)) => right.search(x),
            (Equal, _, _) => Some(x),
            _ => None,
        }
    }
}
2 Likes