Populating a Binary Tree Using Patterns

Building a binary tree is a classic exercise that exposes how a language handles recursive data structures and pointer management. In Rust, the combination of enums, pattern matching, and ownership makes this exercise both instructive and surprisingly concise. The patterns you write are not just syntax—they directly model the shape of the tree and dictate how you traverse, inspect, and modify it.

This section walks through populating a binary search tree (BST) from scratch. Every step will show how pattern matching replaces the manual null checks and pointer indirections you might write in other languages, and how the compiler guides you toward memory-safe tree manipulation.

Why a Binary Tree is a Perfect Case for Enums

A binary tree node is either empty or contains a value and two child trees. That “either empty or a value” structure maps directly to Rust’s Option type and recursive enum variants. Representing the tree with an enum makes the shape of the data explicit and gives the compiler full knowledge of the possible states at every node.

Consider this definition:

#[derive(Debug)]
enum BinaryTree<T: Ord> {
    Empty,
    Node(Box<TreeNode<T>>),
}
#[derive(Debug)]
struct TreeNode<T: Ord> {
    value: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>,
}

BinaryTree is either Empty (no node) or a Node wrapping a heap-allocated TreeNode. The Box is required because a TreeNode contains two more BinaryTree values, which would create an infinitely sized type on the stack. Boxing places the TreeNode on the heap, keeping the enum variant’s size finite and known at compile time.

A simpler, more common variant merges the two types into a single enum, using Box directly in the recursive variant:

#[derive(Debug)]
enum Tree<T: Ord> {
    Empty,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

The three-element tuple variant holds the value, the left child, and the right child. Every Node owns its children, and the ownership tree exactly mirrors the logical tree structure. When you drop the root, the entire tree is recursively deallocated without any manual cleanup.

Now that the tree is defined, pattern matching becomes the natural way to interact with it. Every operation—insertion, search, traversal—will begin by matching on the two possible shapes: Empty or Node.

Inserting a Value: Matching the Tree Shape

The simplest way to populate the tree is to define a recursive insert method that uses match to decide what to do at each node.

impl<T: Ord> Tree<T> {
    fn insert(&mut self, new_value: T) {
        match self {
            Tree::Empty => {
                *self = Tree::Node(
                    new_value,
                    Box::new(Tree::Empty),
                    Box::new(Tree::Empty),
                );
            }
            Tree::Node(value, left, right) => {
                if new_value < *value {
                    left.insert(new_value);
                } else if new_value > *value {
                    right.insert(new_value);
                }
                // If equal, do nothing — BSTs typically ignore duplicates
            }
        }
    }
}

The match block covers both possibilities. When the current node is Empty, the function replaces self with a new leaf node. Because self is a &mut Tree<T>, assigning through the dereference operator *self updates the tree in place. The old Empty is dropped, and the new Node takes its place.

When the current node is Node, the pattern destructures the tuple variant, binding value, left, and right to the appropriate fields. Because self is a mutable reference, left and right are &mut Box<Tree<T>>, which Rust automatically dereferences when you call .insert(new_value) on them. The recursive call follows the same logic until it eventually reaches an Empty leaf.

This pattern-driven approach ensures you never manually check for null or dereference a raw pointer. The compiler enforces that both variants are handled, and the borrow checker guarantees that the recursive mutation does not create aliasing issues.

How Patterns Handle Moving and Borrowing

The destructuring in Tree::Node(value, left, right) => moves the fields out of the node by default. That would be a problem because self is a mutable reference—you cannot move out of a reference. However, the compiler is smart enough to see that the tuple variant holds T, Box<Tree<T>>, and Box<Tree<T>>. When matching a &mut Tree<T>, the pattern binding mode automatically treats the fields as references, so you get &mut T, &mut Box<Tree<T>>, etc. This is called match ergonomics and is why the code above compiles without explicit ref mut annotations.

In older Rust code or when matching through multiple layers of indirection, you might see ref mut used explicitly:

Tree::Node(ref mut value, ref mut left, ref mut right) => { ... }

Match ergonomics make most of that manual work unnecessary today, but understanding it helps when you encounter older examples.

When to Use if let for Single-Variant Interest

If your logic only cares about one variant, if let shortens the code while still providing pattern matching.

impl<T: Ord> Tree<T> {
    fn contains(&self, target: &T) -> bool {
        if let Tree::Node(value, left, right) = self {
            match target.cmp(value) {
                std::cmp::Ordering::Less => left.contains(target),
                std::cmp::Ordering::Greater => right.contains(target),
                std::cmp::Ordering::Equal => true,
            }
        } else {
            false
        }
    }
}

Here, if let destructures the node and immediately provides the inner fields. The else branch handles the Empty case, which simply returns false. Without if let, you would need a full match with two arms, which is equally valid but a few lines longer. Both forms communicate intent clearly; choose the one that fits the surrounding code.

Iterative Insertion with while let

A purely recursive insert is elegant but can hit stack overflow on extremely deep trees in debug builds (release builds may optimize tail recursion, but the borrow checker often prevents tail call optimization). An iterative version using while let and manual traversal avoids that risk while still leaning on patterns.

impl<T: Ord> Tree<T> {
    fn insert_iterative(&mut self, new_value: T) {
        let mut current = self;
        while let Tree::Node(value, left, right) = current {
            if new_value < *value {
                current = left;
            } else if new_value > *value {
                current = right;
            } else {
                return; // duplicate
            }
        }
        // current is &mut Tree::Empty
        *current = Tree::Node(
            new_value,
            Box::new(Tree::Empty),
            Box::new(Tree::Empty),
        );
    }
}

The while let pattern continues as long as current is a Node. Each iteration compares the new value with the current node’s value and moves current to the appropriate child. Once while let fails—meaning current is Tree::Empty—the loop exits, and the code overwrites that Empty with a new leaf.

This version highlights how patterns work not just in match blocks but also in loop conditions. The compiler ensures that current is always a valid mutable reference to some part of the tree, so the final assignment directly updates the correct spot.

Building a Complete Tree: Step-by-Step Walkthrough

The following sequence shows the full lifecycle, from defining the type to inserting multiple values and inspecting the result. Run each step in a Rust project to see the pattern matching in action.

#[derive(Debug)]
enum Tree<T: Ord> {
    Empty,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T: Ord> Tree<T> {
    fn insert(&mut self, value: T) {
        match self {
            Tree::Empty => {
                *self = Tree::Node(
                    value,
                    Box::new(Tree::Empty),
                    Box::new(Tree::Empty),
                );
            }
            Tree::Node(v, left, right) => {
                if value < *v {
                    left.insert(value);
                } else if value > *v {
                    right.insert(value);
                }
            }
        }
    }
}

fn main() {
    let mut tree = Tree::Empty;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    println!("{:#?}", tree);
}

Node(
    5,
    Node(
        3,
        Node(2, Empty, Empty),
        Node(4, Empty, Empty),
    ),
    Node(7, Empty, Empty),
)

Common Mistakes and How Patterns Help Avoid Them

Learning to populate a tree with patterns surfaces several ownership and borrowing mistakes that are common even for experienced Rust developers. Identifying them early saves time.

Mistake: Trying to Match Nested Nodes Directly

Rust does not allow you to match through Box or Option to inspect the inner variants of a child node without first unwrapping them. For example, this code will not compile:

match self {
    Tree::Node(_, Tree::Node(inner_val, ..), _) => { /* ... */ }
}

The compiler sees Tree::Node(..) inside the tuple, but the field is of type Box<Tree<T>>, not Tree<T> directly. You must first reach into the Box with a separate pattern or by dereferencing. A workaround using if let:

if let Tree::Node(value, left, _) = self {
    if let Tree::Node(inner_val, ..) = left.as_ref() {
        // Now inner_val is available
    }
}

as_ref() on Box<Tree<T>> gives an &Tree<T>, which you can then pattern-match against without moving.

Mistake: Duplicate Binding Names in a Pattern

If you try to bind the same name twice in a single pattern to require that two separate fields have identical values, the compiler rejects it:

// Will NOT compile
Tree::Node(x, left, right) if x == x => { /* ... */ }

But the mistake often appears when learners mistakenly write something like:

Tree::Node(val, left, right) if val > *left.unwrap_val() => { /* ... */ }

This isn’t the duplicate binding error, but if you accidentally use val again later in the same pattern without meaning to shadow, you’ll get a warning. The real duplicate binding error surfaces when you write a pattern that binds the same variable name in two different places, like Tree::Node(v, left, right) if matches!(left, Tree::Node(v, ..)) =>. Here v is bound twice. The solution: rename the inner binding to inner_v.

Mistake: Forgetting to Dereference the Value for Comparison

Inside a pattern arm, value from Tree::Node(value, left, right) is a reference when matching a &self or &mut self. To compare it with a new value using < or >, you must dereference it. The original code uses *value for this reason. Forgetting the * causes a type mismatch error because you are comparing &T with T, and the Ord trait requires both sides to be the same type.

Patterns Beyond Insertion: Traversal and Collection

Populating the tree is only the beginning. The same pattern‑matching machinery powers other tree algorithms. An in‑order traversal that collects values into a sorted vector demonstrates how patterns can drive iteration.

impl<T: Ord + Clone> Tree<T> {
    fn inorder(&self) -> Vec<T> {
        match self {
            Tree::Empty => vec![],
            Tree::Node(value, left, right) => {
                let mut result = left.inorder();
                result.push(value.clone());
                result.extend(right.inorder());
                result
            }
        }
    }
}

For a tree containing 5, 3, 7, 2, 4, calling inorder() returns [2, 3, 4, 5, 7]. The match automatically handles the base case and the recursive case, and ownership of the Vec is passed up the call stack without manual memory management.

A while let variant can yield an iterator-like structure for an explicit stack‑based traversal, but for most BST use cases the recursive version is clear enough and benefits from the compiler’s ability to optimize through pattern matches.

Matching Through Indirection: Box and Option Patterns

A subtle point that often trips up newcomers is that you cannot pattern‑match through multiple layers of indirection in one step. Box<Tree<T>> is a smart pointer, not a Tree<T>, so you must first unwrap the box.

The Rust reference clarifies that the left‑hand side of a match arm can only destructure the immediate value. If you have a Box<Tree<T>>, you can match it as Box::new(Tree::Node(...)) directly in a match because Box patterns are supported:

let boxed_tree: Box<Tree<i32>> = Box::new(Tree::Node(10, Box::new(Tree::Empty), Box::new(Tree::Empty)));
match *boxed_tree {
    Tree::Node(value, _, _) => println!("Got {}", value),
    Tree::Empty => println!("Empty"),
}

But inside a parent node where the child field is Box<Tree<T>>, you cannot nest patterns. That’s why the insert method uses left.insert(value) rather than trying to match on **left inline. The call moves the recursion into a new function scope, where the self parameter is again a &mut Tree<T> and standard patterns apply. This is a deliberate design that keeps each pattern match simple and avoids complex nested destructuring that would make ownership harder to reason about.

Summary

Populating a binary tree in Rust is an exercise in letting patterns model your data. The enum defines the two possible shapes—Empty and Node—and pattern matching (match, if let, while let) gives you direct, safe access to both the structure and the values.

The key insights from this exploration:

• Ownership drives the design. Using Box for children enforces a single-owner tree that is automatically cleaned up, and patterns work with the borrow checker rather than against it.
• Pattern matching replaces null checks. Every branch in a match corresponds to a concrete shape of the tree, so there is no risk of forgetting to handle the empty case.
• Match ergonomics reduce boilerplate. When matching a mutable reference, fields are automatically bound as &mut, eliminating the need for explicit ref mut in most modern code.
• Common pitfalls are caught at compile time. Attempting to move out of a reference, binding a name twice, or forgetting to dereference all produce clear errors that point directly to the pattern in question.

This foundation unlocks the rest of the chapter. With a populated tree, you can now explore more advanced pattern forms—like match guards, @ bindings, and destructuring struct variants—to implement balancing, deletion, and tree‑transforming operations.