Binary Search Tree Trim

This post came from a Leetcode problem in February's daily challenges which I solved. It contains a few things that were issues for me when initially learning Rust, namely, how to properly use Rc and RefCell. Now that I understand them a lot more, I thought I'd write about them.

The problem is to trim a binary search tree. Not that long ago my initial reaction to seeing this problem would be 😱 oh no, a tree in Rust! Luckily I have a lot more experience dealing with referential structures now, and I also recently read Learn Rust With Entirely Too Many Linked Lists which is awesome and helped solidify the problems you can encounter with such structures.

The Algorithm

Here is the problem:

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lie in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

The algorithm I came up with is as follows, in pseudocode:

TreeNode {
    val: String,
    left: TreeNode,
    right: TreeNode
}

visit(root: TreeNode, low: int, high: int) -> TreeNode:
    if root is null
        return null;

    if root.val < low:
        return visit(root.right, low, high);

    if root.val > high:
        return visit(root.left, low, high);

    if root.val > low:
        root.left = visit(root.left, low, high);
    else:
        root.left = null

    if root.val < high:
        root.right = visit(root.right, low, high);
    else:
        root.right = null

    return root

Here is a quick animation of how it visits each node and modifies the tree. This tree is created from the list [10, 8, 11, 7, 9, null, 13], low = 8, and high = 12. Click here to start it.

So how does this algorithm translate into Rust, given the real definition of TreeNode?

Pseudo-code to Rust Code

First the tree nodes. These were given by the problem statement.

// Defined in the problem
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

// Defined in the problem
impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub struct Solution;

Let's create two methods trim_bst and visit on Solution.

impl Solution {
    pub fn trim_bst(
        root: Option<Rc<RefCell<TreeNode>>>,
        low: i32,
        high: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        Self::visit(root, low, high)
    }

    fn visit(
        subtree: Option<Rc<RefCell<TreeNode>>>,
        low: i32,
        high: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        unimplemented!()
    }
}

trim_bst just calls visit. unimplemented!() is a macro that will cause a panic if we try to execute it. It allows the code to type check and compile as we add to it. The first step, if the node is None return None.

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    unimplemented!()
}

subtree is an Option so we can use the ?¹ operator on it. Here, let subtree = subtree?; is short for:

let subtree = match subtree {
    Some(val) => val,
    None => return None,
}

Which says - if subtree is None return None, otherwise create a new variable also called subtree and assign the value inside the Option to it. Does it compile?

$ cargo build
...
warning: unused variable: `subtree`
  --> src/day2.rs:38:13
   |
38 |         let subtree = subtree?;
   |             ^^^^^^^ help: if this is intentional, prefix it with an underscore: `_subtree`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `low`
  --> src/day2.rs:35:9
   |
35 |         low: i32,
   |         ^^^ help: if this is intentional, prefix it with an underscore: `_low`

warning: unused variable: `high`
  --> src/day2.rs:36:9
   |
36 |         high: i32,
   |         ^^^^ help: if this is intentional, prefix it with an underscore: `_high`

warning: 3 warnings emitted

    Finished dev [unoptimized + debuginfo] target(s) in 0.35s

It does! Great. There are few warnings for unused variables, we can ignore these for now, we will eventually use them.

Next we need to check if node.val < low and if it is, recursively visit the right subtree, discarding the current node and its left subtree. Not that long ago, trying to do this with Rc<RefCell<T>> would have sent me into a spiral of misery. But that was past me, now I am future me (present me?), and I've learned a lot since then. So here is the next step:

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    let mut subtree_ref = subtree.borrow_mut();
    let right = subtree_ref.right.clone();
    if subtree_ref.val < low {
        return Self::visit(right, low, high);
    }
    unimplemented!()
}

Does it build?

$ cargo build
...
    Finished dev [unoptimized + debuginfo] target(s) in 0.23s

It does, great! A lot is happening here, even though it's just a few lines of code. Let's start by breaking down what exactly let mut subtree_ref = subtree.borrow_mut(); is doing.

Auto-deref on Method Calls

The type of subtree after let subtree = subtree?; is Rc<RefCell<TreeNode>>. Calling borrow_mut will first get a reference to the inner value of Rc, this is a RefCell<TreeNode> here. Then it will borrow the inner value of the RefCell, wrapped in a RefMut, giving us a RefMut<TreeNode>. This all happens because of the Deref impl for Rc and the borrow_mut method on RefCell.

// Deref impl for Rc
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: ?Sized> Deref for Rc<T> {
    type Target = T;

    #[inline(always)]
    fn deref(&self) -> &T {
        &self.inner().value
    }
}
...

// borrow_mut on RefCell
#[stable(feature = "rust1", since = "1.0.0")]
#[inline]
#[track_caller]
pub fn borrow_mut(&self) -> RefMut<'_, T> {
    self.try_borrow_mut().expect("already borrowed")
}

[stable(feature = "try_borrow", since = "1.13.0")]
#[inline]
pub fn try_borrow_mut(&self) -> Result<RefMut<'_, T>, BorrowMutError> {
    match BorrowRefMut::new(&self.borrow) {
        // SAFETY: `BorrowRef` guarantees unique access.
        Some(b) => Ok(RefMut { value: unsafe { &mut *self.value.get() }, borrow: b }),
        None => Err(BorrowMutError { _private: () }),
    }
}

Because of these, when we call borrow_mut on subtree with subtree.borrow_mut() the Rc will automatically be dereferenced² by a call to its Deref impl, and give us the inner RefCell. The call to borrow_mut happens on that RefCell, which will return a RefMut<TreeNode>.

Now subtree_ref is a RefMut<TreeNode> and any method calls on it will deref to calls on a TreeNode because of RefMut's Deref impl. So we can just call subtree_ref.val to get the val field of the node, and given that subtree_ref is a mutable reference, we can mutate it also. That's a lot going on for a single line of code!

Why Do We Clone the Subtree 🤔?

Let's see what happens if we leave out the call to clone when we get the right subtree:

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    let mut subtree_ref = subtree.borrow_mut();
    let right = subtree_ref.right; // clone() is gone
    if subtree_ref.val < low {
        return Self::visit(right, low, high);
    }
    unimplemented!()
}

What does the compiler say?

$ cargo build
...
error[E0507]: cannot move out of dereference of `RefMut<'_, TreeNode>`
  --> src/lib.rs:39:21
   |
39 |         let right = subtree_ref.right;
   |                     ^^^^^^^^^^^^^^^^^ move occurs because value has type `Option<Rc<RefCell<TreeNode>>>`, which does not implement the `Copy` trait
   |
help: consider borrowing the `Option`'s content
   |
39 |         let right = subtree_ref.right.as_ref();
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^
help: consider borrowing here
   |
39 |         let right = &subtree_ref.right;
   |                     ^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0507`.
error: could not compile `rust-trees-post`

What! Thinking about it a bit more it makes sense. We are trying to move³ the value of subtree_ref.right into right, if we did that, what would the value of subtree_ref.right be? Let's apply the suggestion from the compiler to add as_ref and see what happens:

$ cargo build
...
error[E0308]: mismatched types
  --> src/lib.rs:41:32
   |
41 |             return Self::visit(right, low, high);
   |                                ^^^^^ expected struct `Rc`, found reference
   |
   = note: expected enum `Option<Rc<RefCell<TreeNode>>>`
              found enum `Option<&Rc<RefCell<TreeNode>>>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0308`.
error: could not compile `rust-trees-post`

To learn more, run the command again with --verbose.

What!? Oh, the types don't match now. as_ref will give us an Option<&Rc<RefCell<TreeNode>>>, but we want an Option<Rc<RefCell<TreeNode>>>. It is possible to update the type of the subtree arg in the visit method to be Option<&Rc<RefCell<TreeNode>>>, but it would complicate things.

Let's not try that now, and instead put clone back - let right = subtree_ref.right.clone();. So what's happening here?

What the Clone Actually Does

subtree_ref.right is a value of type Option<Rc<RefCell<TreeNode>>>. When we call subtree_ref.right.clone(), we are first calling clone on the Option. The definition of the Clone trait for Option is as follows:

impl<T: Clone> Clone for Option<T> {
    #[inline]
    fn clone(&self) -> Self {
        match self {
            // If the Option is Some, just call clone on the value contained within
            Some(x) => Some(x.clone()),
            None => None,
        }
    }
    ...
}

So it just calls clone on the value inside the Option, if there is one. The value in our Option is of type Rc<RefCell<TreeNode>>. So what does clone for Rc look like?

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: ?Sized> Clone for Rc<T> {
    #[inline]
    fn clone(&self) -> Rc<T> {
        self.inner().inc_strong();
        Self::from_inner(self.ptr)
    }
}

It increments the strong reference count⁴ and calls from_inner. It doesn't really matter here how from_inner works, we just care about what it returns, which is itself (the Rc we called clone on).

So, to sum it up, calling clone on subtree_ref.right will increment the Rc's (strong) reference count and give us back the Option<Rc<RefCell<TreeNode>>> if subtree_ref.right is not None. Or it will just give us None if subtree_ref.right is None.

A Borrow Which Lives Longer Than Expected

Let's add the rest of the algorithm:

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    let mut subtree_ref = subtree.borrow_mut();
    let right = subtree_ref.right.clone();
    if subtree_ref.val < low {
        return Self::visit(right, low, high);
    }

    // After here is new
    let left = subtree_ref.left.clone();
    if subtree_ref.val > high {
        return Self::visit(left, low, high);
    }
    if subtree_ref.val > low {
        subtree_ref.left = Self::visit(left, low, high);
    }
    if subtree_ref.val < high {
        subtree_ref.right = Self::visit(right, low, high);
    }
    Some(subtree)
}

Nothing special here that wasn't covered in the previous section, it matches pretty closely with our pseudocode algorithm. We are now returning the subtree instead of using the unimplemented macro. This should build fine:

$ cargo build
...
error[E0505]: cannot move out of `subtree` because it is borrowed
  --> src/lib.rs:53:14
   |
38 |         let mut subtree_ref = subtree.borrow_mut();
   |                               ------- borrow of `subtree` occurs here
...
53 |         Some(subtree)
   |              ^^^^^^^ move out of `subtree` occurs here
54 |     }
   |     - borrow might be used here, when `subtree_ref` is dropped and runs the destructor for type `RefMut<'_, TreeNode>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0505`.
error: could not compile `rust-trees-post`

Crap, It doesn't build fine! What's it saying? We are mutably borrowing the subtree with let mut subtree_ref = subtree.borrow_mut(); but this borrow is still active when we try to return the subtree from visit. This confused me for a long time when I was learning Rust. RefMut internally holds a value of type BorrowRefMut, in a field called borrow. This type has a custom Drop implementation, a destructor, so when RefMut is dropped this Drop impl will be run.

This custom drop impl counts as a use of RefMut, so the borrow checker is rightly saying it will be used after we return from the function, as RefMut is only dropped once that happens⁵. So we either need to scope the borrow, or explicitly call drop on subtree_ref. Let's just scope the borrow (just put it in a new block):

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    {
        let mut subtree_ref = subtree.borrow_mut();
        let right = subtree_ref.right.clone();
        if subtree_ref.val < low {
            return Self::visit(right, low, high);
        }
        let left = subtree_ref.left.clone();
        if subtree_ref.val > high {
            return Self::visit(left, low, high);
        }
        if subtree_ref.val > low {
            subtree_ref.left = Self::visit(left, low, high);
        }
        if subtree_ref.val < high {
            subtree_ref.right = Self::visit(right, low, high);
        }
    }
    Some(subtree)
}

It should compile now ... 🤞

$ cargo build
...
    Finished dev [unoptimized + debuginfo] target(s) in 0.21s

Awesome! However, we missed a step. If we run the tests it will fail. We will go through the tests in-depth in a moment, you can see them here. The issue is that we never take into account the cases where root.val == low or root.val == high. We do nothing in both those cases. This test builds a tree which looks as follows:

We want to filter out all nodes less than 8 and greater than 12, so the resulting tree should be:

However, the tree we end up with is:

Which is not right at all! 7 shouldn't be there, unless 8 <= 7 <= 12 which I don't believe is true in this universe. Admittedly, it took me a few minutes to realize the actual problem even though I had tests that were failing and the pseudocode algorithm I had outlined had an explicit case handling this 😄. Let's fix it!

Fix That Issue

Ok, so we never deal with the case where the current node is equal to either the low or high bound. What we should do is set the left subtree to None when it's equal to low and the right subtree to None when equal to high. There are a few ways we can fix this, here is one:

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    {
        let mut subtree_ref = subtree.borrow_mut();
        let right = subtree_ref.right.clone();
        if subtree_ref.val < low {
            return Self::visit(right, low, high);
        }
        let left = subtree_ref.left.clone();
        if subtree_ref.val > high {
            return Self::visit(left, low, high);
        }
        subtree_ref.left = if subtree_ref.val > low {
            Self::visit(left, low, high)
        } else {
            None
        };
        subtree_ref.right = if subtree_ref.val < high {
            Self::visit(right, low, high)
        } else {
            None
        };
    }
    Some(subtree)
}

That seems a little wordy. With Rust 1.50 we are able to replace the if/else's in this code with the method then on bool:

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    {
        let mut subtree_ref = subtree.borrow_mut();
        let right = subtree_ref.right.clone();
        if subtree_ref.val < low {
            return Self::visit(right, low, high);
        }
        let left = subtree_ref.left.clone();
        if subtree_ref.val > high {
            return Self::visit(left, low, high);
        }
        subtree_ref.left = (subtree_ref.val > low)
            .then(|| Self::visit(left, low, high))
            .flatten();
        subtree_ref.right = (subtree_ref.val < high)
            .then(|| Self::visit(right, low, high))
            .flatten();
    }
    Some(subtree)
}

However, I think the cleanest solution here is to use take instead of clone.

fn visit(
    subtree: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let subtree = subtree?;
    {
        let mut subtree_ref = subtree.borrow_mut();
        let right = subtree_ref.right.take();   // take instead of clone
        if subtree_ref.val < low {
            return Self::visit(right, low, high);
        }
        let left = subtree_ref.left.take();     // same here
        if subtree_ref.val > high {
            return Self::visit(left, low, high);
        }
        if subtree_ref.val > low {
            subtree_ref.left = Self::visit(left, low, high);
        }
        if subtree_ref.val < high {
            subtree_ref.right = Self::visit(right, low, high);
        }
    }
    Some(subtree)
}

Remember the reason we used clone in the first place? It was because we could not move a given subtree out of the current node. take will give us ownership of the subtree and set None in its place. So in the above code when we assign to right - the line let right = subtree_ref.right.take(); - right now owns the right subtree, and subtree_ref.right is set to None. Later on we re-assign to subtree_ref with the filtered nodes in right if we hit the condition subtree_ref.val < high. Because we use take now if we don't hit that condition it means the value of the current node is equal to high and subtree_ref.right will be None, exactly what we want! The same also happens with left when we take the left subtree.

How Do We Test This?

I had the tests written before the code in this case, so I could validate the implementation was correct. I glossed over them until now because they are more complex than implementing the algorithm itself! First, we need to build a tree given its definition as a list of nodes. Leetcode defines a tree in level order in a list, for example [3, 0, 4, null, 2, null, null, 1] is the tree:

Right, we need a function, say build_tree, which takes a list of nodes specified in level order and gives us a tree. How can we turn a list into a tree?

Planting Our Tree

The first step is to compute the number of levels. With that, we can build the nodes for each level and use a queue to track the nodes for a previous level. The nodes we create at each iteration will then get put into the subtrees of the nodes we have in our queue from the previous iteration. This seems hard to explain in English! Let's just start implementing.

We can get the height of the tree by first taking the length of the node definition list, call it n. Where n > 1 the height is ceil(lg n) (lg being log to the base 2). ceil being the mathematical ceiling function. If n is 1 then there is only one level. Each level has at most 2 ^ level nodes. Level 0 can have 2 ^ 0 = 1, level 1 can have 2 ^ 1 = 2 nodes and so on.

So, if our list has 6 items, including null items, we get ceil(lg 6) == 3. We must have a tree with 3 levels. Let's start with the shell of a build_tree function.

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    unimplemented!()
}

There is no tree if values is empty, and we need to compute the height, lets start there.

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize
    } else {
        1
    };
    unimplemented!()
}

We need to cast length to a floating point value to get the lg of the length, Rust doesn't currently have log methods for integer types⁶. Ok, next up, plant the root of our tree. Thinking ahead a little bit, we're going to want to read the items in the Vec in reverse, so let's also just reverse it.

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize
    } else {
        1
    };
    values.reverse();
    // We know values is not empty so unwrapping is ok
    let initial = values.pop().unwrap()?;
    let root = Rc::new(RefCell::new(TreeNode::new(initial)));
    unimplemented!()
}

Ok, now we have the root. We need queue to track nodes:

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    // Create a queue as a VecDeque
    let mut queue = VecDeque::new();
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize
    } else {
        1
    };
    values.reverse();
    let initial = values.pop().unwrap()?;
    let root = Rc::new(RefCell::new(TreeNode::new(initial)));
    // Add root to the queue, cloning so we increase the ref count and the
    // queue becomes another owner of root
    queue.push_back(root.clone());
    unimplemented!()
}

Great! We use a VecDeque for our queue. Pushing the root on the queue means we start creating the nodes at the next level:

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    let mut queue = VecDeque::new();
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize
    } else {
        1
    };
    values.reverse();
    let initial = values.pop().unwrap()?;
    let root = Rc::new(RefCell::new(TreeNode::new(initial)));
    queue.push_back(root.clone());
    // For 1 to height - 1. For example, if the height is 3 we loop twice as we
    // already took care of the first level which is just root.
    for _ in 1..height {
        // Do something...
        unimplemented!()
    }
}

Growing Our Tree

So what do we do in the loop 🤔? We need to do something for all of the nodes we saw in the last level:

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    let mut queue = VecDeque::new();
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize + 1
    } else {
        1
    };
    values.reverse();
    let initial = values.pop().unwrap()?;
    let root = Rc::new(RefCell::new(TreeNode::new(initial)));
    queue.push_back(root.clone());
    for _ in 1..height {
        // For all the nodes in the previous level
        while let Some(node) = queue.pop_back() {
            // Do something...
        }
    }
    Some(root)
}

The something we need to do is create two nodes at this level and add them to the node we popped off the queue. Lets create a function for node creation, it needs to do a couple of things that are common to both nodes we need to create:

fn construct_subtree(
    values: &mut Vec<Option<i32>>,
    subtree_ref: &mut Option<Rc<RefCell<TreeNode>>>,
    queue: &mut VecDeque<Rc<RefCell<TreeNode>>>,
) {
    if let Some(Some(value)) = values.pop() {
        let node = Rc::new(RefCell::new(TreeNode::new(value)));
        let node_ref = node.clone();
        *subtree_ref = Some(node);
        queue.push_front(node_ref);
    }
}

It creates the new node, adds it to the node we popped off the queue (subtree_ref is this node in the function args), and adds the new node to the queue.

if let Some(Some(value)) = values.pop() might look odd. pop will return None if values is empty, and we model null nodes in values as None as well, so we have two levels of Option values. This says we only want to do something if values has a value and that value is not None.

Inside the if let:

let node = Rc::new(RefCell::new(TreeNode::new(value)));
let node_ref = node.clone();
*subtree_ref = Some(node);
queue.push_front(node_ref);

We construct the new node, clone it to make node_ref another owner, and increment its reference count. Then we assign the value Some(node), our new node, to subtree_ref. We need to dereference it with * to assign to it. subtree_ref is a mutable reference to either the left or right subtree of a node.

Now we can fill out build_tree:

pub fn build_tree(mut values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
    if values.is_empty() {
        return None;
    }
    let mut queue = VecDeque::new();
    let length = values.len();
    let height = if length > 1 {
        (length as f32).log2().ceil() as usize
    } else {
        1
    };
    values.reverse();
    let initial = values.pop().unwrap()?;
    let root = Rc::new(RefCell::new(TreeNode::new(initial)));
    queue.push_front(root.clone());
    for _ in 1..height {
        while let Some(node) = queue.pop_back() {
            // Borrow the node as mutable
            let mut node_ref = node.borrow_mut();
            // Pass mutable references to values, our queue, and to the left subtree
            // to construct_subtree.
            construct_subtree(&mut values, &mut node_ref.left, &mut queue);
            // Similar, but for the right subtree.
            construct_subtree(&mut values, &mut node_ref.right, &mut queue);
        }
    }
    Some(root)
}

Awesome! You can see the full code at wayofthepie/bst-trim-post@3b80b. There is a bit here, but now we can build trees from a Vec. For example, if the tree is defined as [3, 0, 4, null, 2, null, null, 1] we would pass the Vec vec![Some(3), Some(0), Some(4), None, Some(2), None, None, Some(1)] to build_tree.

And with that, we can finally write a test 🎉.

#[test]
fn example1() {
    let root = build_tree(vec![
        Some(10),
        Some(8),
        Some(11),
        Some(7),
        Some(9),
        None,
        Some(13),
    ]);
    let answer = Solution::trim_bst(root, 8, 12);
    let expected = build_tree(vec![Some(10), Some(8), Some(11), None, Some(9), None, None]);
    assert_eq!(
        answer, expected,
        "\nexpected tree \n{:#?}\n got \n{:#?}",
        expected, answer
    );
}

Conclusion

That covers a lot of the issues I used to have with Rc<RefCell<T>> based types when initially learning Rust. I think the only place I've ever seen them used in trees is on Leetcode, but they appear in many other places, and the info in this post is still useful outside of their use in trees. I do find it odd that the trees are defined this way, however. If the TreeNode definition used Box<TreeNode> as the left and right subtrees the problem would be much easier to solve. It seems needlessly complicated for a problem like this. In the next post I'll change the TreeNode definition to use boxed subtrees, instead of Rc<RefCell<TreeNode>> and we'll go through how that changes things.