bst_problem.rs

struct TreeNode<T>
    where T: Ord
{
    value: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

impl TreeNode<T>
    where T: Ord
{
     fn step(&self, value: &T) -> Option<&TreeNode<T>> {
        match value.cmp(&self.value) {
            Ordering::Less => self.left.as_ref().map(|node_box| node_box.deref()),
            Ordering::Equal => Some(&self),
            Ordering::Greater => self.right.as_ref().map(|node_box| node_box.deref()),
        }
    }

    fn step_mut(&mut self, value: &T) -> Option<&mut TreeNode<T>> {
        match value.cmp(&self.value) {
            Ordering::Less => self.left.as_mut().map(|node_box| node_box.deref_mut()),
            Ordering::Equal => Some(self),
            Ordering::Greater => self.right.as_mut().map(|node_box| node_box.deref_mut()),
        }
    }
 
    fn parent(&self, value: &T) -> &TreeNode<T> {
        let mut cursor = self;

        while let Some(next_node) = cursor.step(value) {
            if next_node.value == *value {
                return cursor;
            }

            cursor = next_node;
        }

        return cursor;
    }
  
    fn parent_mut(&mut self, value: &T) -> &mut TreeNode<T> {
        let mut cursor = self;

        while let Some(next_node) = cursor.step_mut(value) {
            if next_node.value == *value {
                return cursor;
            }

            cursor = next_node;
        }

        return cursor;
    }  
}