Trees and tries

In a linked list, each node points to at most one next node. In a tree, each node can point to several nodes, called its children. Trees describe anything organized as a hierarchy. Examples are folders on a disk, the parts of an expression, and a sorted set of numbers arranged for fast search.

Trees are easier to write in Rust than the doubly linked list of chapter 9. Each node has exactly one parent, so a parent can own its children outright, with Box or with a Vec. No Rc or RefCell is needed. The harder parts are elsewhere: replacing a node from inside a method, and choosing between recursion and an explicit stack or queue.

The chapter starts with vocabulary, then binary trees, then binary search trees, then trees with any number of children, and ends with the trie.

11.1 Tree vocabulary

Figure 11.1 names the parts of a tree.

• The root is the one node with no parent. Trees are drawn with the root at the top.
• A leaf is a node with no children.
• The subtree of a node is that node and everything below it. Every subtree is a tree itself. So a function on a tree can call itself on each subtree, which is recursion.
• The depth of a tree is the number of levels from the root down to its deepest leaf.

A binary tree is a tree in which each node has at most two children, called the left child and the right child.

11.2 A binary tree as an enum

A binary tree is either empty, or a node holding a value and two smaller binary trees. That sentence translates directly into an enum:

Listing 11.1 The tree type (lines 1 to 16). src/problems/binary_tree.rs

//! Binary tree as an algebraic data type.
//!
//! ```text
//! Tree = Empty
//!      | Node { value, left: Box<Tree>, right: Box<Tree> }
//! ```

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Tree {
    Empty,
    Node {
        value: i32,
        left: Box<Tree>,
        right: Box<Tree>,
    },
}

The children are Box<Tree> for the reason chapter 8 gave. A Tree cannot contain two Tree values directly, because its size would have no end. A Box is one pointer, so a node has a fixed size.

11.2.1 Depth and inversion

Listing 11.2 Depth and inversion (lines 19 to 35).

impl Tree {
    pub fn max_depth(&self) -> usize {
        match self {
            Tree::Empty => 0,
            Tree::Node { left, right, .. } => 1 + left.max_depth().max(right.max_depth()),
        }
    }

    pub fn invert(&mut self) {
        match self {
            Tree::Empty => {}
            Tree::Node { left, right, .. } => {
                left.invert();
                right.invert();
                std::mem::swap(left, right);
            }
        }
    }
    // ...
}

Each method is a match with two arms. The Empty arm is the base case, the input small enough to answer directly. The Node arm calls the method on the children and combines the results.

max_depth reads as a definition. An empty tree has depth 0. A node has depth 1 plus the larger depth of its two subtrees. For the tree in figure 11.1: the leaves have depth 1, node 20 has depth 2, and the root has depth 3.

invert swaps every node’s left and right children, so the tree becomes its mirror image. It inverts both subtrees first and then calls std::mem::swap(left, right). The pattern binds left and right as mutable references to the boxes, so the swap exchanges two pointers and moves no nodes.

11.2.2 The three depth-first orders

Visiting every node of a tree once is called a traversal. Going down one branch as far as possible before trying the next is depth-first traversal. There are three common depth-first orders. They differ only in when a node is visited relative to its children (figure 11.2).

• Pre-order visits the node first, then its left subtree, then its right subtree.
• In-order visits the left subtree, then the node, then the right subtree.
• Post-order visits both subtrees, then the node.

Listing 11.3 The public traversal methods (lines 37 to 53).

impl Tree {
    // ...
    pub fn preorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_preorder(&mut out);
        out
    }

    pub fn inorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_inorder(&mut out);
        out
    }

    pub fn postorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_postorder(&mut out);
        out
    }
    // ...
}

Each public method creates an empty Vec, passes it to a private helper, and returns it. Creating the vector once and passing it down avoids building a new vector at every node.

Listing 11.4 The recursive helpers (lines 55 to 86).

impl Tree {
    // ...
    fn collect_preorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                out.push(*value);
                left.collect_preorder(out);
                right.collect_preorder(out);
            }
        }
    }

    fn collect_inorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                left.collect_inorder(out);
                out.push(*value);
                right.collect_inorder(out);
            }
        }
    }

    fn collect_postorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                left.collect_postorder(out);
                right.collect_postorder(out);
                out.push(*value);
            }
        }
    }
}

The three helpers are identical except for one line: where out.push(*value) appears relative to the two recursive calls. *value copies the i32 out of the reference.

Listing 11.5 The complete file, with its tests. src/problems/binary_tree.rs

//! Binary tree as an algebraic data type.
//!
//! ```text
//! Tree = Empty
//!      | Node { value, left: Box<Tree>, right: Box<Tree> }
//! ```

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Tree {
    Empty,
    Node {
        value: i32,
        left: Box<Tree>,
        right: Box<Tree>,
    },
}

impl Tree {
    pub fn max_depth(&self) -> usize {
        match self {
            Tree::Empty => 0,
            Tree::Node { left, right, .. } => 1 + left.max_depth().max(right.max_depth()),
        }
    }

    pub fn invert(&mut self) {
        match self {
            Tree::Empty => {}
            Tree::Node { left, right, .. } => {
                left.invert();
                right.invert();
                std::mem::swap(left, right);
            }
        }
    }

    pub fn preorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_preorder(&mut out);
        out
    }

    pub fn inorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_inorder(&mut out);
        out
    }

    pub fn postorder(&self) -> Vec<i32> {
        let mut out = Vec::new();
        self.collect_postorder(&mut out);
        out
    }

    fn collect_preorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                out.push(*value);
                left.collect_preorder(out);
                right.collect_preorder(out);
            }
        }
    }

    fn collect_inorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                left.collect_inorder(out);
                out.push(*value);
                right.collect_inorder(out);
            }
        }
    }

    fn collect_postorder(&self, out: &mut Vec<i32>) {
        match self {
            Tree::Empty => {}
            Tree::Node { value, left, right } => {
                left.collect_postorder(out);
                right.collect_postorder(out);
                out.push(*value);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn leaf(value: i32) -> Tree {
        Tree::Node {
            value,
            left: Box::new(Tree::Empty),
            right: Box::new(Tree::Empty),
        }
    }

    fn node(value: i32, left: Tree, right: Tree) -> Tree {
        Tree::Node {
            value,
            left: Box::new(left),
            right: Box::new(right),
        }
    }

    fn sample() -> Tree {
        node(3, leaf(9), node(20, leaf(15), leaf(7)))
    }

    #[test]
    fn max_depth_works() {
        assert_eq!(Tree::Empty.max_depth(), 0);
        assert_eq!(leaf(1).max_depth(), 1);
        assert_eq!(sample().max_depth(), 3);
    }

    #[test]
    fn invert_swaps_subtrees() {
        let mut tree = sample();
        tree.invert();

        match &tree {
            Tree::Node { left, right, .. } => {
                match left.as_ref() {
                    Tree::Node { value, .. } => assert_eq!(*value, 20),
                    _ => panic!("expected left node"),
                }
                match right.as_ref() {
                    Tree::Node { value, .. } => assert_eq!(*value, 9),
                    _ => panic!("expected right node"),
                }
            }
            _ => panic!("expected node"),
        }
    }

    #[test]
    fn traversals_work() {
        let tree = sample();
        assert_eq!(tree.preorder(), vec![3, 9, 20, 15, 7]);
        assert_eq!(tree.inorder(), vec![9, 3, 15, 20, 7]);
        assert_eq!(tree.postorder(), vec![9, 15, 7, 20, 3]);
    }
}

The test module defines two small helpers, leaf and node, so a test tree can be built in one readable expression. sample() builds the tree of figure 11.1. The traversal test checks all three orders from figure 11.2.

11.3 Binary search trees

A binary search tree (BST) is a binary tree with an ordering rule. For every node, all values in its left subtree are smaller than the node’s value, and all values in its right subtree are larger.

The rule makes searching fast. To find a value, compare it with the root. If it is smaller, it can only be in the left subtree; if larger, only in the right. Each comparison discards one subtree (figure 11.3).

The code for this chapter has two implementations of the same BST. They agree on inserting and searching, and differ in how they remove values and answer range queries. I’ll go through the first fully, then the parts where the second differs.

11.3.1 The type, insertion, and search

Listing 11.6 The type (lines 1 to 14). src/bin/bst_clean.rs

use std::cmp::Ordering;

type TreeLink<T> = Box<BST<T>>;

#[derive(Debug, Clone, Default)]
pub enum BST<T> {
    #[default]
    Empty,
    Node {
        value: T,
        left: TreeLink<T>,
        right: TreeLink<T>,
    },
}

BST<T> is generic over the value type. The methods require T: Ord, meaning values of type T can be ordered, which a search tree needs. #[default] on Empty makes an empty tree the default value, which the removal code uses.

Listing 11.7 Creating, inserting, and searching (lines 17 to 47).

impl<T: Ord> BST<T> {
    pub fn new() -> Self {
        Self::Empty
    }

    pub fn insert(&mut self, val: T) {
        match self {
            Self::Empty => {
                *self = Self::Node {
                    value: val,
                    left: Box::new(Self::Empty),
                    right: Box::new(Self::Empty),
                };
            }
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.insert(val),
                Ordering::Greater => right.insert(val),
                Ordering::Equal => {}
            },
        }
    }

    pub fn contains(&self, val: &T) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.contains(val),
                Ordering::Greater => right.contains(val),
                Ordering::Equal => true,
            },
        }
    }
    // ...
}

insert takes &mut self because it changes the tree in place. It walks down with recursive calls. When it reaches an Empty tree, it replaces that spot with a new leaf: *self = Self::Node { ... }. On the way down, val.cmp(value) compares the new value with the node’s and returns Ordering::Less, Greater, or Equal. A value equal to one already in the tree is ignored, so the tree holds each value once.

contains follows the same path without changing anything.

11.3.2 Removal

Removing a value is the hardest operation, because the tree must keep its ordering rule. There are three cases (figure 11.4).

1. No left child. Replace the node with its right subtree.
2. No right child. Replace the node with its left subtree.
3. Two children. Keep the node, but give it a new value: the smallest value in its right subtree. That value is larger than everything on the left and smaller than everything else on the right, so the rule still holds. Then remove that smallest value from the right subtree. The smallest value has no left child, so its removal is case 1.

Listing 11.8 Removal (lines 49 to 90).

impl<T: Ord> BST<T> {
    // ...
    pub fn remove(&mut self, val: &T) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.remove(val),
                Ordering::Greater => right.remove(val),
                Ordering::Equal => {
                    if left.is_empty() && right.is_empty() {
                        *self = Self::Empty;
                        return true;
                    }
                    if left.is_empty() {
                        *self = *std::mem::take(right);
                        return true;
                    }
                    if right.is_empty() {
                        *self = *std::mem::take(left);
                        return true;
                    }
                    let min_val = right.remove_min().unwrap();
                    *value = min_val;
                    true
                }
            },
        }
    }

    fn remove_min(&mut self) -> Option<T> {
        match self {
            Self::Empty => None,
            Self::Node { left, .. } if left.is_empty() => {
                let node = std::mem::take(self);
                if let Self::Node { value, right, .. } = node {
                    *self = *right;
                    Some(value)
                } else {
                    unreachable!()
                }
            }
            Self::Node { left, .. } => left.remove_min(),
        }
    }
    // ...
}

The first two cases need to replace *self with one of its own children. That is not straightforward, because right is a reference into *self. You cannot move a subtree out through right and assign it to *self in one step. std::mem::take(right) solves it: it moves the subtree out and leaves the default value, an empty tree, in its place. Then *self = *std::mem::take(right) assigns the subtree, and the * moves it out of its Box. take needs Default, which is why the type derives it.

The code also handles a leaf, a node with no children, separately. Case 1 would already cover it.

For case 3, remove_min removes and returns the smallest value of the right subtree. It walks left until it reaches a node whose left child is empty, using a match guard: Self::Node { left, .. } if left.is_empty(). That node holds the smallest value. The method takes the whole node out with std::mem::take(self), puts its right subtree in its place, and returns its value. The if let ... else { unreachable!() } is there because the compiler cannot see that the value taken from a Node arm is a Node. unreachable!() panics if that ever turns out false.

remove returns true if the value was found and removed, and false otherwise, so a caller can tell the two apart.

11.3.3 Range queries

A range query returns every value between a low and a high bound, in order. A BST can answer it without visiting subtrees that cannot contain an answer.

Listing 11.9 Range queries (lines 92 to 114).

impl<T: Ord> BST<T> {
    // ...
    pub fn range(&self, low: &T, high: &T) -> Vec<&T> {
        let mut result = Vec::new();
        self.range_helper(low, high, &mut result);
        result
    }

    // Explicit lifetime 'a ties the references in the vector to the lifetime of &self.
    fn range_helper<'a>(&'a self, low: &T, high: &T, acc: &mut Vec<&'a T>) {
        match self {
            Self::Empty => {}
            Self::Node { value, left, right } => {
                if value < low {
                    right.range_helper(low, high, acc);
                } else if value > high {
                    left.range_helper(low, high, acc);
                } else {
                    left.range_helper(low, high, acc);
                    acc.push(value);
                    right.range_helper(low, high, acc);
                }
            }
        }
    }
    // ...
}

range_helper collects matching values into an accumulator, acc. Its three branches skip work:

• If the node’s value is below low, everything in its left subtree is lower still, so only the right subtree is searched.
• If the value is above high, only the left subtree is searched.
• Otherwise, the helper searches the left subtree, adds the value, and searches the right subtree. That order is in-order traversal, so the results come out sorted.

The signature has an explicit lifetime: fn range_helper<'a>(&'a self, ..., acc: &mut Vec<&'a T>). The references pushed into acc point into the tree, so they must live as long as the tree borrow &'a self. Without the named 'a, the elision rules from chapter 4 would give self and the vector’s elements separate lifetimes. The push would then not compile.

Listing 11.10 The complete program. src/bin/bst_clean.rs

use std::cmp::Ordering;

type TreeLink<T> = Box<BST<T>>;

#[derive(Debug, Clone, Default)]
pub enum BST<T> {
    #[default]
    Empty,
    Node {
        value: T,
        left: TreeLink<T>,
        right: TreeLink<T>,
    },
}

impl<T: Ord> BST<T> {
    pub fn new() -> Self {
        Self::Empty
    }

    pub fn insert(&mut self, val: T) {
        match self {
            Self::Empty => {
                *self = Self::Node {
                    value: val,
                    left: Box::new(Self::Empty),
                    right: Box::new(Self::Empty),
                };
            }
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.insert(val),
                Ordering::Greater => right.insert(val),
                Ordering::Equal => {}
            },
        }
    }

    pub fn contains(&self, val: &T) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.contains(val),
                Ordering::Greater => right.contains(val),
                Ordering::Equal => true,
            },
        }
    }

    pub fn remove(&mut self, val: &T) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { value, left, right } => match val.cmp(value) {
                Ordering::Less => left.remove(val),
                Ordering::Greater => right.remove(val),
                Ordering::Equal => {
                    if left.is_empty() && right.is_empty() {
                        *self = Self::Empty;
                        return true;
                    }
                    if left.is_empty() {
                        *self = *std::mem::take(right);
                        return true;
                    }
                    if right.is_empty() {
                        *self = *std::mem::take(left);
                        return true;
                    }
                    let min_val = right.remove_min().unwrap();
                    *value = min_val;
                    true
                }
            },
        }
    }

    fn remove_min(&mut self) -> Option<T> {
        match self {
            Self::Empty => None,
            Self::Node { left, .. } if left.is_empty() => {
                let node = std::mem::take(self);
                if let Self::Node { value, right, .. } = node {
                    *self = *right;
                    Some(value)
                } else {
                    unreachable!()
                }
            }
            Self::Node { left, .. } => left.remove_min(),
        }
    }

    pub fn range(&self, low: &T, high: &T) -> Vec<&T> {
        let mut result = Vec::new();
        self.range_helper(low, high, &mut result);
        result
    }

    // Explicit lifetime 'a ties the references in the vector to the lifetime of &self.
    fn range_helper<'a>(&'a self, low: &T, high: &T, acc: &mut Vec<&'a T>) {
        match self {
            Self::Empty => {}
            Self::Node { value, left, right } => {
                if value < low {
                    right.range_helper(low, high, acc);
                } else if value > high {
                    left.range_helper(low, high, acc);
                } else {
                    left.range_helper(low, high, acc);
                    acc.push(value);
                    right.range_helper(low, high, acc);
                }
            }
        }
    }

    fn is_empty(&self) -> bool {
        matches!(self, Self::Empty)
    }
}

fn main() {
    let mut bst = BST::new();
    bst.insert(10);
    bst.insert(5);
    bst.insert(15);
    bst.insert(3);
    bst.insert(7);
    bst.insert(12);
    bst.insert(18);

    println!("Contains 7: {}", bst.contains(&7));
    println!("Contains 12: {}", bst.contains(&12));

    let range = bst.range(&4, &16);
    println!("Values in [4, 16]: {:?}", range);

    println!("Remove 5: {}", bst.remove(&5));
    println!("Remove 10: {}", bst.remove(&10));
    println!("Remove 99: {}", bst.remove(&99));

    println!("After removals: {:#?}", bst);
}

$ cargo run --bin bst_clean
Contains 7: true
Contains 12: true
Values in [4, 16]: [5, 7, 10, 12, 15]
Remove 5: true
Remove 10: true
Remove 99: false
After removals: Node {
    value: 12,
    left: Node {
        value: 7,
        left: Node {
            value: 3,
            left: Empty,
            right: Empty,
        },
        right: Empty,
    },
    right: Node {
        value: 15,
        left: Empty,
        right: Node {
            value: 18,
            left: Empty,
            right: Empty,
        },
    },
}

Follow the two removals by hand. Node 5 has two children, 3 and 7. So it takes 7, the smallest value on its right, and the old 7 leaf is removed. Node 10 also has two children, so the root takes 12, the smallest value in its right subtree. The printed tree shows 12 at the root and 7 where 5 was.

11.3.4 A second BST, with an iterative minimum

The second implementation writes removal and range queries differently.

Listing 11.11 Removal and pop_min (lines 49 to 84). src/bin/bst_easy.rs

use std::{
    cmp::Ordering::{Equal, Greater, Less},
    mem,
};

impl<T: Ord> BST<T> {
    // ...
    pub fn remove(&mut self, val: &T) {
        match self {
            Self::Empty => {}
            Self::Node { value, left, right } => match val.cmp(value) {
                Less => left.remove(val),
                Greater => right.remove(val),
                Equal => {
                    if left.is_empty() {
                        *self = right.take();
                    } else if right.is_empty() {
                        *self = left.take();
                    } else {
                        *value = right.pop_min().unwrap();
                    }
                }
            },
        }
    }

    pub fn pop_min(&mut self) -> Option<T> {
        let mut node = self;

        while node.has_left() {
            if let Self::Node { left, .. } = node {
                node = left;
            }
        }

        match node.take() {
            Self::Empty => None,
            Self::Node { value, right, .. } => {
                *node = *right;
                Some(value)
            }
        }
    }
    // ...
}

This remove uses a helper take, defined at the end of the file, that swaps in Empty with mem::replace. So the type does not need Default. right.take() reaches through the Box automatically and returns the tree inside.

pop_min finds the smallest value with a loop instead of recursion. It moves a mutable reference, node, down the left side of the tree:

let mut node = self;
while node.has_left() {
    if let Self::Node { left, .. } = node {
        node = left;
    }
}

When the loop ends, node refers to the leftmost node. match node.take() splits it into its value and its right subtree, with no unreachable!. The loop uses one stack frame however deep the tree is. pop_min is also public, so the tree can serve as a queue that always returns the smallest value.

Listing 11.12 A range query that returns a new vector (lines 86 to 102).

impl<T: Ord> BST<T> {
    // ...
    pub fn range(&self, from: &T, to: &T) -> Vec<&T> {
        let mut result = Vec::new();

        if let Self::Node { value, left, right } = self {
            if from < value {
                result.extend(left.range(from, to));
            }
            if from <= value && value <= to {
                result.push(value);
            }
            if value < to {
                result.extend(right.range(from, to));
            }
        }

        result
    }
    // ...
}

This range returns a new Vec from each call and joins the children’s results with extend. It is shorter than the accumulator version, and it allocates a vector at every node it visits, where the accumulator version allocates one.

Listing 11.13 The complete program. src/bin/bst_easy.rs

use std::{
    cmp::Ordering::{Equal, Greater, Less},
    mem,
};

#[derive(Debug, Clone)]
pub enum BST<T> {
    Empty,
    Node {
        value: T,
        left: Box<BST<T>>,
        right: Box<BST<T>>,
    },
}

impl<T: Ord> BST<T> {
    pub fn new() -> Self {
        Self::Empty
    }

    pub fn insert(&mut self, val: T) {
        match self {
            Self::Empty => {
                *self = Self::Node {
                    value: val,
                    left: Box::new(Self::Empty),
                    right: Box::new(Self::Empty),
                };
            }
            Self::Node { value, left, right } => match val.cmp(value) {
                Less => left.insert(val),
                Greater => right.insert(val),
                Equal => {}
            },
        }
    }

    pub fn contains(&self, val: &T) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { value, left, right } => match val.cmp(value) {
                Less => left.contains(val),
                Greater => right.contains(val),
                Equal => true,
            },
        }
    }

    pub fn remove(&mut self, val: &T) {
        match self {
            Self::Empty => {}
            Self::Node { value, left, right } => match val.cmp(value) {
                Less => left.remove(val),
                Greater => right.remove(val),
                Equal => {
                    if left.is_empty() {
                        *self = right.take();
                    } else if right.is_empty() {
                        *self = left.take();
                    } else {
                        *value = right.pop_min().unwrap();
                    }
                }
            },
        }
    }

    pub fn pop_min(&mut self) -> Option<T> {
        let mut node = self;

        while node.has_left() {
            if let Self::Node { left, .. } = node {
                node = left;
            }
        }

        match node.take() {
            Self::Empty => None,
            Self::Node { value, right, .. } => {
                *node = *right;
                Some(value)
            }
        }
    }

    pub fn range(&self, from: &T, to: &T) -> Vec<&T> {
        let mut result = Vec::new();

        if let Self::Node { value, left, right } = self {
            if from < value {
                result.extend(left.range(from, to));
            }
            if from <= value && value <= to {
                result.push(value);
            }
            if value < to {
                result.extend(right.range(from, to));
            }
        }

        result
    }

    fn is_empty(&self) -> bool {
        match self {
            Self::Empty => true,
            Self::Node { .. } => false,
        }
    }

    fn has_left(&self) -> bool {
        match self {
            Self::Empty => false,
            Self::Node { left, .. } => !left.is_empty(),
        }
    }

    fn take(&mut self) -> Self {
        mem::replace(self, Self::Empty)
    }
}

fn main() {
    let mut bst = BST::new();

    bst.insert(10);
    bst.insert(5);
    bst.insert(15);
    bst.insert(3);
    bst.insert(7);
    bst.insert(12);

    println!("Contains 7: {}", bst.contains(&7));
    println!("Range 4 to 12: {:?}", bst.range(&4, &12));

    bst.remove(&10);
    println!("After removing 10: {:?}", bst.range(&0, &100));

    println!("Pop min: {:?}", bst.pop_min());
    println!("{:#?}", bst);
}

$ cargo run --bin bst_easy
Contains 7: true
Range 4 to 12: [5, 7, 10, 12]
After removing 10: [3, 5, 7, 12, 15]
Pop min: Some(3)

11.4 Trees with any number of children

Many real trees are not binary. A folder can hold any number of files and folders. A node that owns a Vec<TreeNode<T>> of children describes such a tree. It needs no Box, because the Vec already keeps its elements on the heap, so the node’s own size is fixed.

11.4.1 Depth first and breadth first

Figure 11.5 shows the two basic ways to visit such a tree. A depth-first visit goes down one branch completely before starting the next, as in section 11.2.2. A breadth-first visit goes level by level: the root, then all its children, then all their children.

Depth first is naturally recursive. Breadth first needs a queue: a collection where items leave in the order they arrived. You put the root in the queue. Then, repeatedly, you take the node at the front, visit it, and add its children at the back. Because children join at the back, every node of one level leaves the queue before any node of the next.

A node owns its value and a Vec of child nodes. The children are stored inside the vector itself, not behind pointers, so a node can have any number of them:

use std::collections::VecDeque;

struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>, // Owned children directly inline
}

Listing 11.14 The complete program. src/bin/test_tree.rs

use std::collections::VecDeque;

struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>, // Owned children directly inline
}

impl<T> TreeNode<T>
where
    T: Clone + std::fmt::Display,
{
    /// Recursive DFS (Pre-order) - No callbacks
    pub fn dfs(&self) {
        println!("{}", self.value);
        for child in self.children.iter() {
            child.dfs();
        }
    }

    /// Level Order BFS - Idiomatic VecDeque::from([self])
    pub fn bfs(&self) {
        let mut queue = VecDeque::from([self]); // Idiomatic initialization

        while let Some(node) = queue.pop_front() {
            println!("{}", node.value);

            for child in &node.children {
                queue.push_back(child);
            }
        }
    }
}

fn main() {
    // --- Inline Construction (No variables, no push) ---

    let root = TreeNode {
        value: 1,
        children: vec![
            TreeNode {
                value: 2,
                children: vec![
                    TreeNode {
                        value: 4,
                        children: vec![],
                    },
                    TreeNode {
                        value: 5,
                        children: Vec::new(),
                    },
                ],
            },
            TreeNode {
                value: 3,
                children: vec![TreeNode {
                    value: 6,
                    children: Vec::new(),
                }],
            },
        ],
    };

    println!("=== DFS ===");
    root.dfs();
    // Output: 1, 2, 4, 5, 3, 6

    println!("\n=== BFS ===");
    root.bfs();
    // Output: 1, 2, 3, 4, 5, 6
}

dfs prints the node and then calls itself on each child, which is pre-order.

bfs uses a VecDeque as the queue. VecDeque::from([self]) starts it with the root. The queue holds references, &TreeNode<T>, so no node is moved or copied. pop_front takes from the front, and push_back adds each child at the back.

The tree in main is written as one nested value. The shape of the code matches the shape of the tree, which makes test data easy to check.

$ cargo run --bin test_tree
=== DFS ===
1
2
4
5
3
6

=== BFS ===
1
2
3
4
5
6

11.4.2 Grouping values by level

A common variation returns the values grouped by level, as a list of lists. The first list holds the root’s value, the second the values of its children, and so on. The file solves it twice.

Listing 11.15 The type and the first version (lines 1 to 20). src/bin/tree_under_pressure.rs

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>,
}

fn level_order<T>(root: &TreeNode<T>) -> Vec<Vec<&T>> {
    let mut result = Vec::new();
    let mut level = vec![root];
    while !level.is_empty() {
        result.push(level.iter().map(|n| &n.value).collect());
        level = level
            .iter()
            .flat_map(|n| &n.children)
            .collect();
    }
    result
}

level_order keeps one whole level in level, a Vec of references to nodes. Each pass of the loop does two things. It adds the values of this level to the result. Then it builds the next level from all the children of all the nodes in this level: level.iter().flat_map(|n| &n.children).collect(). flat_map turns each node into its children and joins all those children into one sequence. The loop ends when a level has no nodes.

Listing 11.16 The second version, with a queue (lines 22 to 40).

fn level_order_readable<T>(root: &TreeNode<T>) -> Vec<Vec<&T>> {
    let mut result = Vec::new();
    let mut queue = VecDeque::from([(root)]);

    while !queue.is_empty() {
        let current_size = queue.len();
        let mut level = Vec::with_capacity(current_size);

        for _ in 1..=current_size {
            let Some(node) = queue.pop_front() else { break };

            level.push(&node.value);
            queue.extend(&node.children);
        }

        result.push(level);
    }
    result
}

level_order_readable uses one queue, as bfs did. The trick is queue.len() at the start of each round. At that moment, the queue holds exactly one level. So the loop pops exactly that many nodes, collecting their values, while their children pile up behind them for the next round.

let Some(node) = queue.pop_front() else { break }; is a let-else statement. It binds node if the pattern matches, and runs the else block, which must leave the loop or the function, if it does not. queue.extend(&node.children) adds references to all the children at once.

Listing 11.17 The complete program. src/bin/tree_under_pressure.rs

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>,
}

fn level_order<T>(root: &TreeNode<T>) -> Vec<Vec<&T>> {
    let mut result = Vec::new();
    let mut level = vec![root];
    while !level.is_empty() {
        result.push(level.iter().map(|n| &n.value).collect());
        level = level
            .iter()
            .flat_map(|n| &n.children)
            .collect();
    }
    result
}

fn level_order_readable<T>(root: &TreeNode<T>) -> Vec<Vec<&T>> {
    let mut result = Vec::new();
    let mut queue = VecDeque::from([(root)]);

    while !queue.is_empty() {
        let current_size = queue.len();
        let mut level = Vec::with_capacity(current_size);

        for _ in 1..=current_size {
            let Some(node) = queue.pop_front() else { break };

            level.push(&node.value);
            queue.extend(&node.children);
        }

        result.push(level);
    }
    result
}

fn main() {
    let root: TreeNode<String> = TreeNode {
        value: "root".into(),
        children: vec![
            TreeNode {
                value: "branch_a".into(),
                children: vec![
                    TreeNode {
                        value: "leaf_1".into(),
                        children: vec![],
                    },
                    TreeNode {
                        value: "leaf_2".into(),
                        children: vec![],
                    },
                ],
            },
            TreeNode {
                value: "branch_b".into(),
                children: vec![TreeNode {
                    value: "leaf_3".into(),
                    children: vec![],
                }],
            },
        ],
    };

    let levels = level_order(&root);
    println!("Tree\n {:#?}", root);

    for level in levels {
        println!("{:?}", level);
    }

    println!("one queue, one level per round:");
    for level in level_order_readable(&root) {
        println!("{:?}", level);
    }
}

main prints the tree with {:#?}, then the levels from each version. Both give the same three levels:

["root"]
["branch_a", "branch_b"]
["leaf_1", "leaf_2", "leaf_3"]
one queue, one level per round:
["root"]
["branch_a", "branch_b"]
["leaf_1", "leaf_2", "leaf_3"]

Both functions return Vec<Vec<&T>>, references into the tree, and both run in O(n).

11.5 Saving a tree to a file and loading it back

To save a tree, you turn it into a flat sequence of text. Later, you rebuild exactly the same tree from that text. Turning a structure into a flat sequence is called serialization.

A list of values in pre-order is not enough, because it does not say where one node’s children end. The file’s format adds, after each value, the number of children that follow (figure 11.6). A reader can then rebuild the tree: read a value and a count, then read that many subtrees.

Listing 11.18 The tree type, and writing the pairs (lines 1 to 47). src/bin/tree_serializ_deserialize_into_file.rs

use std::{collections::VecDeque, fs, io, str::FromStr};

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>,
}

impl<T> TreeNode<T> {
    // ...
    fn serialize(&self) -> Vec<String>
    where
        T: ToString,
    {
        let mut serialized = Vec::new();
        let mut stack = vec![self];

        while let Some(node) = stack.pop() {
            serialized.push(node.value.to_string());
            serialized.push(node.children.len().to_string());

            for child in node.children.iter().rev() {
                stack.push(child);
            }
        }

        serialized
    }
    // ...
}

TreeNode<T> is the same shape as in section 11.4: a value and a Vec of child nodes. A node can have any number of children.

serialize walks the tree in pre-order without recursion, using a Vec as a stack: the last item pushed is the first popped. It pushes the children in reverse order, with iter().rev(), so that the first child is on top and is popped first. For each node it writes the value and the child count as strings.

The line where T: ToString sits on the method, not on the whole impl. So a tree of any type exists, and only a tree whose values can become strings gets a serialize method.

Listing 11.19 Reading the pairs back (lines 49 to 63).

impl<T> TreeNode<T> {
    // ...
    fn deserialize(serialized: &[String], pos: &mut usize) -> Option<Self>
    where
        T: FromStr,
    {
        let value = serialized.get(*pos)?.parse().ok()?;
        let child_count: usize = serialized.get(*pos + 1)?.parse().ok()?;
        *pos += 2;

        let mut children = Vec::new();
        for _ in 0..child_count {
            children.push(Self::deserialize(serialized, pos)?);
        }

        Some(TreeNode { value, children })
    }
    // ...
}

deserialize is recursive. pos is a &mut usize, a position in the token list shared by all the calls. Each call reads a value and a count at pos, advances pos by two, and then calls itself child_count times to read the children.

Every step that can fail uses ? on an Option. The failures are a missing token, a value that does not parse, and a count that is not a number. .parse().ok()? first turns the parse Result into an Option. Any failure makes the whole function return None.

Listing 11.20 The complete program. src/bin/tree_serializ_deserialize_into_file.rs

use std::{collections::VecDeque, fs, io, str::FromStr};

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    children: Vec<TreeNode<T>>,
}

impl<T> TreeNode<T> {
    fn level_order(&self) -> Vec<Vec<&T>> {
        let mut result = Vec::new();
        let mut queue = VecDeque::from([self]);

        while !queue.is_empty() {
            let current_size = queue.len();
            let mut level = Vec::with_capacity(current_size);

            for _ in 1..=current_size {
                let Some(node) = queue.pop_front() else { break };
                level.push(&node.value);
                queue.extend(&node.children);
            }

            result.push(level);
        }

        result
    }

    fn serialize(&self) -> Vec<String>
    where
        T: ToString,
    {
        let mut serialized = Vec::new();
        let mut stack = vec![self];

        while let Some(node) = stack.pop() {
            serialized.push(node.value.to_string());
            serialized.push(node.children.len().to_string());

            for child in node.children.iter().rev() {
                stack.push(child);
            }
        }

        serialized
    }

    fn deserialize(serialized: &[String], pos: &mut usize) -> Option<Self>
    where
        T: FromStr,
    {
        let value = serialized.get(*pos)?.parse().ok()?;
        let child_count: usize = serialized.get(*pos + 1)?.parse().ok()?;
        *pos += 2;

        let mut children = Vec::new();
        for _ in 0..child_count {
            children.push(Self::deserialize(serialized, pos)?);
        }

        Some(TreeNode { value, children })
    }

    fn save(&self, path: &str) -> io::Result<()>
    where
        T: ToString,
    {
        fs::write(path, self.serialize().join("\n"))
    }

    fn load(path: &str) -> Option<Self>
    where
        T: FromStr,
    {
        let text = fs::read_to_string(path).ok()?;
        let serialized: Vec<String> = text.lines().map(String::from).collect();
        Self::deserialize(&serialized, &mut 0)
    }
}

fn main() -> io::Result<()> {
    let root = TreeNode {
        value: "root".to_string(),
        children: vec![
            TreeNode {
                value: "a".to_string(),
                children: vec![
                    TreeNode {
                        value: "a1".to_string(),
                        children: vec![],
                    },
                    TreeNode {
                        value: "a2".to_string(),
                        children: vec![],
                    },
                ],
            },
            TreeNode {
                value: "b".to_string(),
                children: vec![TreeNode {
                    value: "b1".to_string(),
                    children: vec![],
                }],
            },
        ],
    };

    root.save("tree.bin")?;

    let Some(loaded) = TreeNode::<String>::load("tree.bin") else {
        println!("invalid tree file");
        return Ok(());
    };

    for level in loaded.level_order() {
        println!("{:?}", level);
    }

    Ok(())
}

save joins the tokens with newlines and writes the file. load reads the file, splits it into lines, and starts reading at position 0 with &mut 0. main saves a tree, loads it back, and prints its levels to show the shape survived:

$ cargo run --bin tree_serializ_deserialize_into_file
["root"]
["a", "b"]
["a1", "a2", "b1"]

The format breaks if a value contains a newline, because the reader splits on newlines. For arbitrary text, write each value’s length before it, or use a serialization library such as serde.

11.6 A trie for finding words by prefix

A trie (usually pronounced “try”) stores a set of words by sharing their common beginnings. Each edge is one character. Walking from the root along the characters of a word leads to the node for that word. A flag on the node marks whether a stored word ends there (figure 11.7).

A prefix is the beginning of a word: "gp" is a prefix of "gpu". A trie answers “is any stored word starting with this prefix?” by walking the prefix’s characters. That makes it the usual structure behind autocompletion.

A trie is one root node. Each node maps a character to the child node for that character, and terminal marks a node where a stored word ends:

pub struct Trie {
    root: Node,
}

#[derive(Default)]
struct Node {
    children: HashMap<char, Node>,
    terminal: bool,
}

Listing 11.21 The complete file. src/problems/trie.rs

//! Trie / prefix tree.
//!
//! Used for autocomplete, command completion, and prefix matching.

use std::collections::HashMap;

#[derive(Default)]
pub struct Trie {
    root: Node,
}

#[derive(Default)]
struct Node {
    children: HashMap<char, Node>,
    terminal: bool,
}

impl Trie {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_default();
        }
        node.terminal = true;
    }

    pub fn search(&self, word: &str) -> bool {
        self.find_node(word)
            .is_some_and(|node| node.terminal)
    }

    pub fn starts_with(&self, prefix: &str) -> bool {
        self.find_node(prefix).is_some()
    }

    fn find_node(&self, word: &str) -> Option<&Node> {
        let mut node = &self.root;
        for ch in word.chars() {
            node = node.children.get(&ch)?;
        }
        Some(node)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn trie_insert_search_and_prefix() {
        let mut trie = Trie::new();
        trie.insert("gpu");
        trie.insert("gpucloud");

        assert!(trie.search("gpu"));
        assert!(trie.search("gpucloud"));
        assert!(!trie.search("gp"));
        assert!(!trie.search("gpucloudapi"));

        assert!(trie.starts_with("gp"));
        assert!(trie.starts_with("gpucloud"));
        assert!(!trie.starts_with("cpu"));
    }
}

Each Node has a HashMap from a character to a child node, and a terminal flag. Both types derive Default, so an empty node is Node::default().

insert walks a mutable cursor, node, down the word, one character per line:

node = node.children.entry(ch).or_default();

entry(ch).or_default() finds the child for ch, creating an empty one if it is missing, and returns a mutable reference to it. Assigning that to node moves the cursor down one level. After the last character, the node is marked terminal.

find_node walks the same way without changing anything. node.children.get(&ch)? returns None from the function at the first missing character. search then checks that the node exists and is terminal, with is_some_and. starts_with only checks that the node exists.

Searching for a word of m characters takes m steps, whatever the number of stored words. A HashMap per node is flexible but uses a lot of memory. For words of lowercase English letters only, an array of 26 child pointers per node is faster and smaller.

Chapter 12 generalizes trees to graphs, where any node can connect to any other, and cycles are possible.

Exercises

1. Write an in-order traversal of the binary tree from listing 11.1 without recursion, using a Vec of references as a stack.
2. Add a height method to one of the BSTs. Insert the numbers 1 to 1,000 in order, then in shuffled order, and compare the heights.
3. Serialize a binary tree using a marker such as # for each empty child, and write the matching reader.
4. Add words_with_prefix(&self, prefix: &str) -> Vec<String> to the trie.