Step 2 of 7

Trees with Box

Lists have one "next" pointer per node. Trees have several: a node points at its children, and each child is a smaller tree. Box handles that the same way.

Expression trees

A calculator, a spreadsheet or a compiler stores a formula like (2 + 3) * 4 as a tree: the * node has two children, the + node and the number 4. Evaluating it is a short recursive function:

enum Expr {
    Num(i64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

use Expr::{Add, Mul, Num};

fn eval(e: &Expr) -> i64 {
    match e {
        Num(n) => *n,
        Add(a, b) => eval(a) + eval(b),
        Mul(a, b) => eval(a) * eval(b),
    }
}

fn main() {
    // (2 + 3) * 4
    let formula = Mul(
        Box::new(Add(Box::new(Num(2)), Box::new(Num(3)))),
        Box::new(Num(4)),
    );
    println!("{}", eval(&formula));
}

20

• Each variant that holds sub-expressions holds them in Boxes. Num is a leaf: it has no children, so the recursion stops there.
• Num(n) => *n: matching through a reference gives n: &i64, so *n copies the number out.
• eval(a): a is a &Box<Expr> and deref coercion turns it into the &Expr that eval wants.

Building trees with Box::new everywhere gets noisy. Small helper functions like fn num(n: i64) -> Box<Expr> { Box::new(Num(n)) } make the code read like the formula.

Binary search trees with Option<Box>

When a child may be missing, use Option<Box<Node>>: None means "no child here". A binary search tree keeps smaller keys on the left and larger ones on the right, so walking it left-to-right visits the keys in sorted order:

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

fn insert(tree: &mut Option<Box<Node>>, key: i32) {
    match tree {
        None => *tree = Some(Box::new(Node { key, left: None, right: None })),
        Some(node) => {
            if key < node.key {
                insert(&mut node.left, key);
            } else {
                insert(&mut node.right, key);
            }
        }
    }
}

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

fn main() {
    let mut root = None;
    for key in [50, 30, 70, 20, 40] {
        insert(&mut root, key);
    }
    let mut keys = Vec::new();
    in_order(&root, &mut keys);
    println!("{keys:?}");
}

[20, 30, 40, 50, 70]

• insert takes &mut Option<Box<Node>>: a mutable reference to "the spot where a child goes". If the spot is empty (None), it puts a new node there with *tree = Some(...). Otherwise it recurses into the correct side.
• Some(node) gives node: &mut Box<Node>; node.key and &mut node.left reach through the Box automatically.

Common mistakes

• Option<Node> without the Box: the struct contains itself again, so you get error[E0072]: recursive type `Node` has infinite size. Option doesn't add a pointer; Box does.
• Returning n instead of *n in Num(n) => ...: n is a &i64, so it's error[E0308]: mismatched types.
• Getting the order wrong for subtraction: in Sub(a, b), it's eval(a) - eval(b), left minus right.

Your task

The calculator gained two operations: Sub(a, b) (a minus b) and Neg(e) (minus e). Write fn eval(e: &Expr) -> i64 for all five variants.

Challenge 2

Write fn show(e: &Expr) -> String that prints a formula with every operation in parentheses:

• Num(7) shows as 7
• Add(2, 3) shows as (2 + 3), Mul uses *
• so (2 + 3) * 4 shows as ((2 + 3) * 4)

Challenge 3

Build a binary search tree of order ids. Using the Node struct below (smaller keys go left, equal or larger go right), write:

• insert(tree: &mut Option<Box<Node>>, key: u32)
• contains(tree: &Option<Box<Node>>, key: u32) -> bool: walk down one side at each node, don't visit the whole tree.
• height(tree: &Option<Box<Node>>) -> usize: the number of nodes on the longest path from the root down (empty tree: 0, one node: 1).

Previous: Box: a value on the heap Next: Deref and Drop: what makes a pointer smart