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


#1
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))


#2

Regarding this:

value: Option<i32>, // data feild

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

value: i32, // data feild


#3

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)


#4

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.


#5

Firstly, @rustacean, 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


#6

@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.


#7

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
        }
    }
}

#8

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
}

#9

+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,
        }
    }
}