How to get minimum BST element?

user_13778698 0
Viewed 58

Given this BST struct:

pub enum BST{
    Nil,
    Node{
        k: i32,
        l: Box<BST>,
        r: Box<BST>,
    }
}

How can a function be programmed such that it gives the minimum element of the BST?

I tried some things, my latest attempt is:

fn min(&mut self) -> &mut BST{
        match self {
            BST::Nil => self,
            BST::Node{ l, ..} =>
                match **l {
                    BST::Nil => self,
                    BST::Node{..} => l.min(),
                }
        }
}

however this doesnt work, the purpose of the min function is to work on BST deletions.

rust binary-search-tree
2 Answers

Writing a function which takes and returns a mutable borrow is very restrictive; roughly speaking, anything you return — by match or by function call — can never stop being borrowed within that scope, even if you don't actually return it, which is a problem for your function because you want to inspect the tree and then possibly return self instead of a component of self. I tried a few possibilities and came up with this version which the compiler accepts:

impl BST {
    fn min(&mut self) -> &mut BST {
        match self {
            BST::Nil => self,
            BST::Node { l, .. } if matches!(**l, BST::Nil) => self,
            BST::Node { l, .. } => l.min(),
        }
    }
}

I think the key element that makes this borrow-checker-friendly is that there are two completely separate match arms (and thus separate patterns) for the two Node possibilities: in the second arm, l is temporary, and in the third arm, l is returned (with modification by .min()), but these two cases have separate bindings for l and thus they can have different lifetimes.

(It's a little silly to write matches! inside a match guard, but we can't actually write a single pattern because of the Box; if box_patterns becomes a stable feature then we'll be able to write a single pattern like BST::Node { l: box BST::Nil, .. }.)

user_996920

I think the way to solve this is to break down your problem into simpler steps. I.e. instead of doing two matches at once, you could only do a single one at a time, this way it also compiles:

pub enum BST {
    Nil,
    Node { k: i32, l: Box<BST>, r: Box<BST> },
}

impl BST {
    fn min(&mut self) -> &mut BST {
        match self {
            BST::Nil => self,
            BST::Node { l, .. } => l.min(),
        }
    }
}

UPDATE: Actually, as @Kevin Reid noticed this changes the semantics of the code, because the second match in OP returned self instead of l.

In my opinion, this makes the function inconsistent, because you either want the minimum element (with is actually is always Nil or the Node before it, which would make the self in the outer match invalid, should be a panic! instead).

However, if you want to get the Node before the minimal element (that would be Nil), you should go around this special case of returning a Nil if called on a Nil. In my opinion, this can be best reflected in the type system by restructuring the BST type like in the following. Here, min_node returns always the "node" which has a "nil" (i.e. None) in l, however, the user can only create "nodes":

#[derive(Debug)]
pub struct BstNode {
    k: i32,
    l: Option<Box<BstNode>>,
    r: Option<Box<BstNode>>,
}

impl BstNode {
    fn min_node(&mut self) -> &mut BstNode {
        if let Some(ref mut l) = self.l {
            l.min_node()
        } else {
            self
        }
    }
}
user_88093100
Related