# 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 `?`1 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.

It would also be a good idea to have some tests here as we build this. You can see the tests I had at wayofthepie/bst-trim-post@3b80b, there is a bit to them. I'll go into more detail on this later.

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

[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 dereferenced2 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

error: could not compile `rust-trees-post`
``````

What! Thinking about it a bit more it makes sense. We are trying to move3 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

error: could not compile `rust-trees-post`

``````

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

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

It would be good to have tests for this function also, but it's currently only used within tests, so just said I'd skip that 😆.

``````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 types6. 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.

Why are we going to read them in reverse? We're going to pop them off the Vec - treating the Vec like a stack - and pop will remove the last element in the Vec. There are other ways to do this, but this seems the most straightforward here.

``````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!(
"\nexpected tree \n{:#?}\n got \n{:#?}",
);
}
``````

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

2

See Method-call Expressions for more on how automatic dereferencing works.

3

If you don't understand what I mean by move here, have a read of this section of The Rust Programming Language Book.

4

If it's not clear what a strong reference is, have a read of the std::rc module docs.

5

The best explanation I've found of why a custom `Drop` impl extends the lifetime is The area covered by a lifetime in the nomicon. It may also be mentioned elsewhere, like the The Rust Programming language but I can't remember seeing it there. It's something that seems obvious now but was very very confusing when I started with Rust.

6

There is a PR discussing adding these to the standard library, see rust-lang/rust#80918.