Published on 12th of August, 2017 · Updated on 15th of April, 2020

Of Boxes and Trees - Smart Pointers in Rust

Recently, I tried to implement a binary tree data structure in Rust. Each binary tree has a root value, a left, and a right subtree. I started from this Python implementation, which is quite straightforward.

class Tree:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

This allows us to declare a fancy tree object like this:

t = Tree(15,
      Tree(12,
           None,
           Tree(13)),
      Tree(22,
           Tree(18),
           Tree(100)))

And the result can be visualized beautifully.
(Yes I’ve drawn that myself.)

Porting that code to Rust turned out to be a little… challenging. My first attempt looked quite innocuous.

struct Tree {
  root: i64,
  left: Tree,
  right: Tree,
}

That’s pretty much a one-to-one translation of the Python definition — but rustc says no.

error[E0072]: recursive type `Tree` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Tree {
  | ^^^^^^^^^^^ recursive type has infinite size
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable

Coming from memory-managed languages (like Python, PHP, or Ruby), I was confused by this. The problem is easy to understand, though. Computers have a limited amount of memory. It’s the compiler’s job to find out how much memory to allocate for each item.

In our case, it infers the following:

A tree is a structure containing an i64, and two trees. Each of these trees is a structure containing an i64, and two trees. Each of these…
You get the idea.

Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore

Since we don’t know how many subtrees our tree will have, there is no way to tell how much memory we need to allocate up front. We’ll only know at runtime!

Rust tells us how to fix that: by inserting an indirection like Box, Rc, or &. These are different “pointer types” in Rust. They all point to places in memory. So, instead of knowing the total size of our tree structure, we just know the point in memory where the tree is located. But that’s enough to define the tree structure. These pointer types allow us to do that safely and without manual memory management. They all offer different guarantees and you should choose the one that fits your requirements best.

• & is called a borrow in Rust speech. It’s the most common of the three. It’s a reference to some place in memory, but it does not own the data it points to. As such, the lifetime of the borrow depends on its owner. Therefore we would need to add lifetime parameters here. This can make it tedious to use.

  struct Tree<'a> {
    root: i64,
    left: &'a Tree<'a>,
    right: &'a Tree<'a>,
  }
  

• Box is a smart pointer with zero runtime overhead. It owns the data it points to and stores it on the heap. We call it smart because when it goes out of scope, it will first drop the data it points to and then itself. No manual memory management required, which is neat. ✨

  struct Tree {
    root: i64,
    left: Box<Tree>,
    right: Box<Tree>,
  }
  

• Rc is another smart pointer. It’s short for “reference-counting”. It keeps track of the number of references to the data structure internally. As soon as the number of references is down to zero, it cleans up after itself. Choose Rc if you need to have multiple owners of the same data in one thread. For multithreading, there’s also Arc (atomic reference count).

  struct Tree {
    root: i64,
    left: Rc<Tree>,
    right: Rc<Tree>,
  }
  

Putting the tree into a box

All three options are totally valid. Which one you should choose, depends on your use-case. A rule of thumb is to keep it simple. In my case, I chose to use a Box, because I did not need any special guarantees.

Making subtrees optional

The next problem I faced was that I could not instantiate a tree structure. The left and right subtree have the type Box<Tree>, but at some point I would need an empty subtree.

In the Python example, I used None to signal the end of my data structure. Thanks to Rust’s Option type we can do the same:

struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

After all of this, we can create our first tree:

Tree {
    root: 15,
    left: Some(Box::new(Tree {
            root: 12,
            left: None,
            right: Some(Box::new(Tree {
                    root: 13,
                    left: None,
                    right: None,
            })),
    })),
    right: Some(Box::new(Tree {
            root: 22,
            left: Some(Box::new(Tree {
                    root: 18,
                    left: None,
                    right: None,
            })),
            right: Some(Box::new(Tree {
                    root: 100,
                    left: None,
                    right: None,
            })),
    })),
};

Depending on your point of view, you might say this is either verbose or explicit. Compared to the Python version, it looked a bit too cluttered for my taste.

Can we do better? Chris McDonald helped me come up with the following representation:

Tree::new(15)
  .left(
    Tree::new(12)
      .right(Tree::new(13))
  )
  .right(
    Tree::new(22)
      .left(Tree::new(18))
      .right(Tree::new(100))
  );

To me, this is much easier on the eye.
Here’s the full tree implementation that makes this possible:

#[derive(Default)]
struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

impl Tree {
  fn new(root: i64) -> Tree {
    Tree {
      root: root,
      ..Default::default()
    }
  }

  fn left(mut self, leaf: Tree) -> Self {
    self.left = Some(Box::new(leaf));
    self
  }

  fn right(mut self, leaf: Tree) -> Self {
    self.right = Some(Box::new(leaf));
    self
  }
}

Update: Danny Grein mentioned on Twitter, that we can support the following syntax by implementing From<i64> for Tree:

root(15)
  .left(
    root(12)
      .right(13)
   )
  .right(
    root(22)
      .left(18)
      .right(100)
  );

Why did it just work in Python?

Now you might be wondering why our tree implementation worked so flawlessly in Python. The reason is that Python dynamically allocates memory for the tree object at runtime. Also, it wraps everything inside a PyObject, which is kind of similar to Rc from above — a reference-counted smart pointer.

Rust is more explicit here. It gives us more flexibility to express our needs but we also need to know about all the possible alternatives to make good use of them. My advice is to stay away from smart pointers if a simple borrow will do.

If lifetimes get in the way however or you need additional guarantees like thread-safety, smart pointers are a great addition to your toolkit. The Rust documentation is a good starting point to learn more about smart pointers. Also, read “Idiomatic tree and graph-like structures in Rust” for some clever use of allocators in case your tree needs to be mutable at runtime.

• 💬 Comments on Reddit.

Sponsor me on Github My Amazon wish list