Rust community has elaborated the concept of reference, ownership and lifetime more than enough. Even after reading tons of resources, such as the ownership, borrowing, lifetime trilogy on their book of 1.8.0 and Understanding Ownership on their book of current version. I still had a hard time to make my code compilable. Especially, when you have to deal with other concepts in Rust such as smart pointers. That was the pain I went through when I was trying to just implement something as simple as tree equality. Even if I was telling me 3000 times of the In this article, I’m gonna go over some concepts that are critical to understanding the code in subsections. If you already understand those concept, just go ahead and skip those subsections.
Problem to solve
The problem is to verify if two binary trees are identical. That means both trees are not only structually identical and the nodes on their respective same position have the same value.
It’s a simple problem you might have already seen and solved in your data structure class. And yes, it’s a trivial problem for OOP language such as Java. It’s simply verify if two nodes have the same value, and recursively compare their left and right children, since two identical trees should have identical left subtree and right subtree as well.
Interface for our tree node
I’m gonna give the conclusion here first and break it down into pieces, so whoever already understand what’s happening can skip the explanation parts.
(The original TreeNode code came from Leetcode, where I learn programming by solving algorithm problems.)
Why are all those wrappers around children?
Option<_>
The Option allows children to have None value, the TreeNode::new implementation is a good example. This is trivial.
Rc<_>
The purpose of Rc<> is to allow multiple ownership to data, which is against the default ownership rule that only one place can have ownership to some data.
We can only use pointer for recursive structure like tree, otherwise, the compiler can’t decide the size of the structure.
Though we can have multiple immutable reference at once, we can’t do it either, because we can’t guarantee that reference won’t outlive the data. Rc<> , however, makes sure that data will stay alive as long as there are strong reference to it.
The example in chapter 15.4 of The Rust Programming Language is a good one, if you haven’t read it, it’s worth your time to take a look.
RefCell<> :
Remember the two important mutual exclusive Rust rules:
- There can only be one mutable reference to a value;
- There can be multiple immutable reference to a value;
Of course we can’t have this restrictions to our tree nodes. We DO want to have both mutable and immutable reference to it. The RefCell<> allows both rules exist together that’s why we need it. And that’s called interior mutability.
Trait for compare
We definitely want to assert equality like the code below.
Then we need to implement Eq and PartialEq traits. This post explains what’s the difference. The short answer is: they are almost the same, except that Eq also dictates reflexive rule: for any value Athat has Eq, A==A is always true. This is trivial and that’s why we don’t have to implement Eq and only have to implement ParitalEq
The rest of implementation
The part checking two nodes have the same value is trivial. The part recursively checking equality is a little bit tricky because we have to deal with reference and smart pointers.
Also note that checking left child and right child equality are the same code, so we can define an anonymous function to better reuse code, which leads to the code below.
Note that we pass in a reference to comparator because otherwise, the Option lifetime will end in the comparator.
Another tricky part here is that we have a reference to Option in the comparator , but the unwrap requires the ownership of the Option . If we call unwrap inside the scope, unwrap will try to get the ownership from the reference, which is disallowed by Rust and we will get cannot move out of borrowed content error. In this case, we need to call to as_ref method from our Option as this requires just a reference and will return another Option with a reference (of course!) to the data in the original Option. And below is the complete implementation.
