Trees in Rust

Think of a family tree, or the folders on your laptop. One folder at the top holds other folders, and each of those holds more. Nothing loops back, and every folder (except the top one) sits inside exactly one other.

That is a tree. It is like a linked list where each node can point to more than one next node. The first node is the root. A node below another is its child, and the node above is its parent. A node with no children is a leaf. Any node together with everything below it is a subtree, which is a smaller tree in its own right.

In a binary tree, each node has at most two children, called the left and the right. A binary search tree (BST) adds one rule: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger.

That rule is what makes it useful. Reach for a BST when you want to keep values in sorted order and find them quickly. Trees also describe anything that nests: folders inside folders, the parts of a sentence, or the way a maths expression is built from smaller expressions.

The picture shows a BST with seven values. To search for 40, start at the root, 50. Since 40 is smaller than 50, go left to 30. Since 40 is larger than 30, go right, and there it is. Three nodes visited, and the other four never touched.

Every comparison throws away a whole subtree. If the tree is well spread out, which is called balanced, each step cuts the remaining nodes roughly in half. Doubling the number of values adds only one more step. That growth is written O(log n), and it is why searching a million values takes about twenty steps.

The catch is the shape. If you insert already-sorted values one after another (1, 2, 3, 4 and so on), every new value goes to the right of the last, and the tree becomes a list with extra steps. Searching then visits every node, which is O(n). So the speed depends on the height, the number of levels from the root down to the lowest leaf.

Remember: in a search tree, every comparison lets you ignore a whole side. That is where the speed comes from.

Trees are a good place to meet recursion: a function that solves a problem by calling itself on a smaller piece. A tree is a natural fit, because a tree is a node plus two smaller trees. A recursive function needs a base case, an answer that needs no more calls. For trees it is nearly always "an empty tree".

A node owns its two children, the same way a linked list node owns the next node in lesson 3. A child is either missing or present, which is Option<Box<Node>> again.

use std::cmp::Ordering;

/// One node. It owns its value and, if present, its two children.
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

/// A binary search tree: smaller values to the left, larger to the right.
pub struct Bst {
    root: Option<Box<Node>>,
    len: usize,
}

impl Bst {
    pub fn new() -> Self {
        Bst { root: None, len: 0 }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    /// Adds a value. Returns `false` if it was already there.
    pub fn insert(&mut self, value: i32) -> bool {
        let added = insert_into(&mut self.root, value);
        if added {
            self.len += 1;
        }
        added
    }

    /// Looks for a value by walking down from the root.
    pub fn contains(&self, value: i32) -> bool {
        let mut current = &self.root;
        while let Some(node) = current {
            match value.cmp(&node.value) {
                Ordering::Equal => return true,
                Ordering::Less => current = &node.left,
                Ordering::Greater => current = &node.right,
            }
        }
        false
    }
}

/// `link` is an empty slot or a node. An empty slot is where the value goes.
fn insert_into(link: &mut Option<Box<Node>>, value: i32) -> bool {
    match link {
        None => {
            *link = Some(Box::new(Node {
                value,
                left: None,
                right: None,
            }));
            true
        }
        Some(node) => match value.cmp(&node.value) {
            Ordering::Less => insert_into(&mut node.left, value),
            Ordering::Greater => insert_into(&mut node.right, value),
            Ordering::Equal => false,
        },
    }
}

impl Default for Bst {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• Node has a value and two optional children. Bst holds the root and a count.
• insert_into takes link, a mutable reference to a slot that is either empty or holds a node. If it is empty (None), that is where the value belongs, so it fills the slot. If it holds a node, value.cmp(&node.value) compares the two and returns an Ordering: Less, Greater or Equal. The function then calls itself on the left or right slot. Equal means the value is already there, so nothing is added.
• contains follows the same path in a loop instead of recursion. current is a shared reference that moves down to &node.left or &node.right. It never needs to change anything, so it only borrows.

Now the walks. The values in a BST come out in sorted order if you visit the left subtree, then the node, then the right subtree. That visiting order is called in-order.

impl Bst {
    /// All the values in sorted order: left subtree, then this node, then right.
    pub fn in_order(&self) -> Vec<i32> {
        let mut out = Vec::with_capacity(self.len);
        collect_in_order(&self.root, &mut out);
        out
    }

    /// The number of levels. An empty tree has height 0.
    pub fn height(&self) -> usize {
        height_of(&self.root)
    }
}

fn collect_in_order(link: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(node) = link {
        collect_in_order(&node.left, out);
        out.push(node.value);
        collect_in_order(&node.right, out);
    }
}

fn height_of(link: &Option<Box<Node>>) -> usize {
    match link {
        None => 0,
        Some(node) => 1 + height_of(&node.left).max(height_of(&node.right)),
    }
}

collect_in_order is recursive. For a node, it first handles everything on the left, then pushes the node's value, then handles everything on the right. When the link is None, the if let finds nothing, and that is the base case. height_of is the same shape: an empty link has height 0, and any other node is 1 plus the taller of its two sides.

The demo in the Playground builds a tree from seven values that arrive in a good order, which has height 3. It then inserts seven values that arrive already sorted, and that tree has height 7.

One honest limit: deleting a value is the fiddliest part of a BST, so we don't build it here. Also, a very lopsided tree makes the recursion go as deep as the tree is tall, which could overflow the stack, as the long linked list did in lesson 3. Balanced trees avoid this.

Rust's standard library has no general-purpose Tree type, since trees come in so many shapes. What it does have are sorted collections that are trees inside. BTreeSet and BTreeMap keep their keys in order and stay balanced, so they never degrade to a list.

use std::collections::BTreeSet;

let mut set = BTreeSet::new();
for value in [50, 30, 70, 20, 40] {
    set.insert(value);
}

let sorted: Vec<i32> = set.iter().copied().collect();
println!("{:?}", sorted);
assert_eq!(sorted, [20, 30, 40, 50, 70]); // always in order
assert!(set.contains(&40));
assert_eq!(set.first(), Some(&20));
assert_eq!(set.last(), Some(&70));

The values come back in order without you doing anything, and first and last give the smallest and largest. Inside, a B-tree keeps many values in each node, so the tree is wide and shallow, and that suits how computers read memory. Lesson 9 covers BTreeMap and range queries in full.

So when do you write your own tree? When the shape is the point: a tree of folders, a parse tree, or a trie (lesson 11). When you only need a sorted collection, use a BTreeSet or BTreeMap.

The height is the key. For a balanced tree, h is about log n, so insert and search are O(log n). For a lopsided tree, h can be n, and they are O(n). A BTreeSet stays balanced for you, so its insert and search are always O(log n).

These use a node type with public fields, so you can build trees and check results. node builds a node from a value and two optional children, and leaf builds a node with none. Open the Playground link to get all of it with each problem.

/// A node for the practice problems. Its fields are public so a test can
/// build and inspect trees.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub value: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

/// Builds a node from a value and two optional children.
pub fn node(
    value: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
) -> Option<Box<TreeNode>> {
    Some(Box::new(TreeNode { value, left, right }))
}

/// A node with no children.
pub fn leaf(value: i32) -> Option<Box<TreeNode>> {
    node(value, None, None)
}

The functions borrow the tree as &Option<Box<TreeNode>>. They only read it, and the caller keeps ownership.

pub fn max_depth(root: &Option<Box<TreeNode>>) -> usize {
    todo!("the number of levels; an empty tree has 0")
}

pub fn max_depth(root: &Option<Box<TreeNode>>) -> usize {
    match root {
        None => 0,
        Some(node) => 1 + max_depth(&node.left).max(max_depth(&node.right)),
    }
}

pub fn is_valid_bst(root: &Option<Box<TreeNode>>) -> bool {
    todo!("every node must fit between the limits set by all its ancestors")
}

pub fn is_valid_bst(root: &Option<Box<TreeNode>>) -> bool {
    // `low` and `high` are the limits from the ancestors. Both are exclusive.
    fn check(link: &Option<Box<TreeNode>>, low: Option<i32>, high: Option<i32>) -> bool {
        let Some(node) = link else {
            return true; // an empty tree is fine
        };
        if low.is_some_and(|low| node.value <= low) {
            return false;
        }
        if high.is_some_and(|high| node.value >= high) {
            return false;
        }
        // Going left, this value becomes the upper limit. Going right, the lower.
        check(&node.left, low, Some(node.value)) && check(&node.right, Some(node.value), high)
    }
    check(root, None, None)
}

pub fn level_order(root: &Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    todo!("the values level by level, left to right")
}

pub fn level_order(root: &Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    use std::collections::VecDeque;

    let mut levels = Vec::new();
    let mut queue = VecDeque::new();
    if let Some(top) = root {
        queue.push_back(top);
    }

    while !queue.is_empty() {
        let mut level = Vec::new();
        // Everything in the queue right now belongs to one level.
        for _ in 0..queue.len() {
            let Some(node) = queue.pop_front() else {
                break;
            };
            level.push(node.value);
            if let Some(left) = &node.left {
                queue.push_back(left);
            }
            if let Some(right) = &node.right {
                queue.push_back(right);
            }
        }
        levels.push(level);
    }
    levels
}

Tree questions are everywhere in coding tests, and almost all of them are recursion in disguise. A few habits help.

• Start with the base case. For nearly every tree problem, ask "what is the answer for an empty tree?" first. Then ask how the answer for a node follows from the answers for its two children.
• Know the traversal names. In pre-order you handle the node, then left, then right. In-order is left, node, right, which gives a BST's values in sorted order. Post-order is left, right, node. Level order, from problem 3, uses a queue.
• Pass information down. Problem 2 shows the trick: when a node's answer depends on its ancestors, carry the limits down as extra arguments.
• Ask about the shape. Is the tree balanced? Can values repeat? Is it a binary search tree, or just a binary tree? The answers decide which tricks are available.
• Say the cost in terms of height. "O(h), which is O(log n) if the tree is balanced and O(n) if it is not" is a complete and honest answer. Mention the recursion's stack use too.
• In Rust, show you know why the types look as they do. Option<Box<Node>> means "maybe a child, which this node owns". Borrowing with &node.left instead of cloning shows that you understand ownership.

Made by VeraStack Labs