I Built a Binary Tree in Rust. This Time the Borrow Checker Was on My Side

Part of the Data Structures in Rust series.

After the linked list experience, I approached the binary tree with the kind of cautious optimism you develop after being burned once. The linked list had fought me at every turn, the recursive structure that seemed natural became an ownership nightmare, and the workarounds felt like arguing with the compiler rather than working with it. The binary tree was going to be different, I told myself, without being entirely sure why.

It was different. Not because trees are simpler than linked lists in any abstract sense, but because the ownership model that made linked lists painful turns out to be exactly the right model for trees. A tree node owns its children. Each child owns its children. Ownership flows in one direction, from parent to child, all the way down to the leaves. That is not a constraint you have to work around. That is just what a tree is.

The structure that actually works

A binary search tree node in Rust looks like this:

#[derive(Debug)]
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

If you just came from the linked list article, this looks familiar. Box<Node> for the recursive reference, Option to represent the absence of a child. The difference is what happens when you start using it. A linked list has one next pointer and removing a node from the middle requires mutable access to the node before it and the node being removed simultaneously, two mutable references to different parts of the same structure, which is exactly what Rust prohibits. A binary tree node has two children, but you never need to hold mutable references to a parent and a child at the same time. You traverse down, you find the insertion point, you modify that node, and you are done. The path from root to any node is a strict chain of ownership, and you follow it one step at a time.

The full tree structure:

#[derive(Debug)]
struct BinarySearchTree {
    root: Option<Box<Node>>,
}

impl BinarySearchTree {
    fn new() -> Self {
        BinarySearchTree { root: None }
    }
}

Insertion without fighting the compiler

Inserting into a binary search tree means walking the tree until you find the right empty spot and placing a new node there. In Rust, the natural approach is to write a recursive function that takes a mutable reference to an Option<Box<Node>> and either inserts at that point or recurses into a child.

impl BinarySearchTree {
    fn insert(&mut self, value: i32) {
        insert_node(&mut self.root, value);
    }
}

fn insert_node(node: &mut Option<Box<Node>>, value: i32) {
    match node {
        None => {
            // Found the empty spot, place the new node here
            *node = Some(Box::new(Node {
                value,
                left: None,
                right: None,
            }));
        }
        Some(existing) => {
            if value < existing.value {
                insert_node(&mut existing.left, value);
            } else if value > existing.value {
                insert_node(&mut existing.right, value);
            }
            // if value == existing.value, ignore duplicates
        }
    }
}

This compiles on the first attempt. No Rc, no RefCell, no fighting with multiple mutable borrows. The function takes a mutable reference to Option<Box<Node>>, pattern matches on whether it is None or Some, and in the Some branch, borrows the existing node to look at its value and recurse into one of its children. At every point there is exactly one mutable reference in play, which is all Rust requires.

The reason this works cleanly where the linked list removal did not is the direction of access. During insertion, you only ever move forward through the tree, from parent to child, holding one mutable reference at a time. You never need to look backward, never need to modify a node while also holding a reference to its parent. The borrow checker has no objections because there is genuinely nothing unsafe happening.

Searching the tree

Search is even cleaner because it only needs immutable references:

fn contains(node: &Option<Box<Node>>, value: i32) -> bool {
    match node {
        None => false,
        Some(existing) => {
            if value == existing.value {
                true
            } else if value < existing.value {
                contains(&existing.left, value)
            } else {
                contains(&existing.right, value)
            }
        }
    }
}

impl BinarySearchTree {
    fn contains(&self, value: i32) -> bool {
        contains(&self.root, value)
    }
}

Multiple immutable references to the tree can exist simultaneously in Rust with no conflict. While searching, you borrow each node immutably, look at its value, decide which child to recurse into, and move on. At each step, the borrow scope ends before moving deeper into the tree, so there is never a moment where two borrows are alive at once that would cause a conflict.

In-order traversal

A binary search tree traversed in-order, left subtree then root then right subtree, produces values in sorted order. This is one of the properties that makes BSTs useful and it falls out of the structure naturally:

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

impl BinarySearchTree {
    fn sorted_values(&self) -> Vec<i32> {
        let mut result = Vec::new();
        in_order(&self.root, result);
        result
    }
}

The result vector gets passed as a mutable reference through every recursive call, accumulating values as the traversal visits each node. You could also write this returning a Vec from each call and concatenating, but passing a mutable accumulator avoids allocating a new vector at every level of recursion, which matters when the tree is large.

Deletion and where things get interesting

Deletion is the hardest operation on a binary search tree, in any language, because removing a node with two children requires finding a replacement that preserves the BST property. In Rust specifically, taking a value out of a Box requires ownership, which means you need to consume the Box to get at the Node inside.

Option::take() appears again here, the same trick that made linked list removal workable. It replaces the Option with None and gives you ownership of what was there, ending the borrow before you use the owned value:

fn delete_node(node: &mut Option<Box<Node>>, value: i32) {
    if let Some(n) = node {
        if value < n.value {
            delete_node(&mut n.left, value);
        } else if value > n.value {
            delete_node(&mut n.right, value);
        } else {
            // Found the node to delete
            *node = match (n.left.take(), n.right.take()) {
                (None, None) => None,           // leaf node, just remove it
                (Some(left), None) => Some(left), // one child, replace with it
                (None, Some(right)) => Some(right),
                (Some(mut left), Some(right)) => {
                    // Two children: find in-order successor (smallest in right subtree)
                    // and replace this node's value with it
                    // For brevity, merge right subtree into left's rightmost position
                    attach_right(&mut left, right);
                    Some(left)
                }
            };
        }
    }
}

fn attach_right(node: &mut Box<Node>, subtree: Box<Node>) {
    if node.right.is_none() {
        node.right = Some(subtree);
    } else {
        attach_right(node.right.as_mut().unwrap(), subtree);
    }
}

The two-children case is simplified here for clarity. A production implementation would find the in-order successor properly, copy its value into the current node, and then delete the successor from the right subtree. The principle is the same: take() to get ownership, match on what you have, restructure.

What changes between the linked list and the tree

The linked list removal required mutable access to adjacent nodes at the same time: hold a reference to the node before the target to update its next pointer while also needing the target's next to skip over it. The tree deletion never requires this. You find the target, take its children with take(), and decide what to put in its place, all while holding the mutable reference to just that one slot in the tree. The parent's reference to the deleted node gets replaced through the node parameter itself, not through a separate reference to the parent.

This is the structural difference that makes trees fit Rust’s ownership model naturally. A tree’s ownership is hierarchical and one-directional. A linked list’s ownership wants to be bidirectional or shared, and Rust’s default model does not accommodate that without extra machinery.

Putting it together

fn main() {
    let mut tree = BinarySearchTree::new();

    for value in [5, 3, 7, 1, 4, 6, 8] {
        tree.insert(value);
    }

    println!("Contains 4: {}", tree.contains(4));  // true
    println!("Contains 9: {}", tree.contains(9));  // false

    let sorted = tree.sorted_values();
    println!("Sorted: {:?}", sorted);  // [1, 3, 4, 5, 6, 7, 8]

    tree.delete(3);
    let after_delete = tree.sorted_values();
    println!("After deleting 3: {:?}", after_delete);  // [1, 4, 5, 6, 7, 8]
}

The linked list article ended with the observation that linked lists are basically the worst case for Rust’s ownership model. Binary trees are close to the best case, because the natural ownership semantics of a parent owning its children map directly onto what Rust’s type system can express without any workarounds. The same Box and Option combination that felt like a constraint in the linked list context becomes the natural and correct representation here.

The next data structure worth building in Rust is a hash map, where the interesting question shifts from ownership to hashing, collision resolution, and how the standard library’s HashMap makes decisions you can only appreciate once you have tried to build one yourself.

If you missed the linked list article, it covers why the same Box and Option combination that works cleanly here becomes a genuine fight in a singly linked list:

[embed]I Tried to Build a Linked List in Rust. The Borrow Checker Had Other Plans There is a rite of passage every Rust learner goes through, usually within the first month, and it has nothing to do…medium.com

The field guide covers ownership, smart pointers, and the full mental model that makes both of these implementations click.

$7 — Zero to Rust: A Systems Programmer’s Field Guide You can read the free sample here — Free 20-page sample