Step 6 of 7

Binary trees with Option<Box<Node>>

A tree is a connected graph with no cycles. A rooted tree has one node at the top (the root); every other node has exactly one parent, and nodes without children are leaves. File systems, HTML documents, org charts and parsed source code are trees.

In a binary tree each node has at most two children, left and right. A binary search tree (BST) adds a rule: everything in a node's left subtree is smaller than the node, and everything in its right subtree is bigger. Searching walks down one path, so it takes O(height): O(log n) when the tree is balanced, but O(n) when it degenerates into a line (insert sorted data into a plain BST and that's exactly what you get). The standard library's BTreeMap is a balanced tree; at work you use it. Building a BST yourself is a classic interview exercise, and it teaches how Rust handles recursive data.

The node type

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

• Option: a child may be missing (None). Rust has no null pointers.
• Box: a pointer to a value on the heap. Without it, a Node would contain two Nodes, each containing two more... an infinite size:

struct Node {
    value: i32,
    next: Option<Node>,
}

fn main() {}

error[E0072]: recursive type `Node` has infinite size

A Box is always one pointer big, so Option<Box<Node>> has a fixed size (and thanks to a niche optimization, it's no bigger than the Box itself).

Inserting and walking

Recursion fits trees perfectly, since every subtree is a tree. Insertion works on the slot where a node might go, a &mut Option<Box<Node>>: an empty slot gets the new node; otherwise go left or right.

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn insert(slot: &mut Option<Box<Node>>, value: i32) {
    match slot {
        None => *slot = Some(Box::new(Node { value, left: None, right: None })),
        Some(node) => {
            if value < node.value {
                insert(&mut node.left, value);
            } else if value > node.value {
                insert(&mut node.right, value);
            } // equal: already in the tree
        }
    }
}

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

fn main() {
    let mut root = None;
    for v in [50, 30, 70, 20, 40, 60, 80, 30] {
        insert(&mut root, v);
    }
    let mut values = Vec::new();
    in_order(&root, &mut values);
    println!("{values:?}");
    if let Some(node) = &root {
        println!("root {} has left child {:?}", node.value, node.left.as_ref().map(|n| n.value));
    }
}

[20, 30, 40, 50, 60, 70, 80]
root 50 has left child Some(30)

The orders of visiting a tree have names. In-order (left, node, right) gives a BST's values sorted. Pre-order (node first) is how you'd copy or print a tree top-down; post-order (node last) is how you'd compute folder sizes or free memory bottom-up; level-order (row by row) is BFS with a VecDeque.

To walk down without recursion, option.as_deref() turns an &Option<Box<Node>> into an Option<&Node>, which is easy to loop with:

let mut cur = root.as_deref();
while let Some(node) = cur {
    cur = if target < node.value { node.left.as_deref() } else { node.right.as_deref() };
}

Common mistakes

• Option<Node> without the Box: infinite size, as above.
• Moving out of a borrowed tree. match &root { Some(node) => ... } borrows; match root { ... } moves the whole tree into the match. Match on a reference when you only want to look.
• Deep recursion on degenerate trees. A BST built from 100,000 sorted values is a 100,000-deep line; recursive walks would overflow the stack. Balanced trees (like BTreeMap) don't have this problem.

Your task

The seed has a Bst with a working insert. Add three methods:

• fn contains(&self, value: i32) -> bool, walking down iteratively with as_deref()
• fn height(&self) -> usize: the number of nodes on the longest path from the root down (0 for an empty tree, 1 for just a root)
• fn sorted(&self) -> Vec<i32>: all values in ascending order (an in-order walk)

Write recursive helper functions on &Option<Box<Node>> for height and sorted.

Challenge 2

Write fn levels(root: &Option<Box<Node>>) -> Vec<Vec<i32>> that lists the values of a binary tree level by level (row by row from the top, left to right within a row). For the tree with root 50, children 30 and 70, and grandchildren 20, 40 and 80, that's [[50], [30, 70], [20, 40, 80]].

It's BFS on a tree: a VecDeque<&Node> starting with the root. Process the queue one level at a time: note how many nodes it holds at the start of a level, pop exactly that many, and push their children.

Challenge 3

Someone hand-edited a tree in a data file. Write fn is_valid_bst(root: &Option<Box<Node>>) -> bool that checks the BST rule: every value in a node's left subtree is smaller than the node and every value in its right subtree is bigger (no duplicates).

Checking only each node against its direct children isn't enough: in the tree with root 10, left child 5 and 5's right child 12, every parent-child pair looks fine, but 12 is in 10's left subtree. Instead, pass down the allowed range: a recursive helper takes low: Option<i32> and high: Option<i32>, the bounds every value in this subtree must stay strictly between.

Previous: Dijkstra's shortest paths with BinaryHeap Next: Union-find (disjoint sets)