We've spent a lot of time with Vec and HashMap, but there are times when you need your data to stay sorted while allowing for fast insertions and lookups. That's where a Binary Search Tree (BST) comes in. To keep this concrete, let's build a UserRegistry. Imagine we're building a system that maps usernames (strings) to user IDs (integers), and we want to be able to iterate through them alphabetically without sorting the whole list every time.

Defining the Node Structure

In Rust, recursive data structures are a bit of a puzzle because the compiler needs to know exactly how much space a type takes up at compile time. If a Node contains another Node, it's infinitely large.

I'll be honest: every time I start a new project in a different language, I occasionally forget that Rust handles this differently than Java or Python. I initially tried to define my node like this:

// This will NOT compile
struct Node {
    username: String,
    id: u32,
    left: Option<Node>, 
    right: Option<Node>,
}

The compiler immediately yelled at me with a "recursive type has infinite size" error. To fix this, we need indirection. By wrapping the child nodes in a Box, we're telling Rust to put the child node on the heap. The Box itself has a fixed size (it's just a pointer), which makes the compiler happy.

struct Node {
    username: String,
    id: u32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

pub struct UserRegistry {
    root: Option<Box<Node>>,
}

Wiring up the Insertion Logic

Now we need a way to put users into the tree. The rule for a BST is simple: smaller values (alphabetically, in our case) go left, larger values go right. Since we're dealing with Option<Box<Node>>, the cleanest way to handle this is by using a mutable reference to the current node we're inspecting.

Check out how I'm using a helper function here. I prefer this approach because it keeps the public API clean while allowing the recursion to handle the heavy lifting.

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

    pub fn insert(&mut self, username: String, id: u32) {
        let mut current = &mut self.root;

        while let Some(ref mut node) = current {
            if username < node.username {
                current = &mut node.left;
            } else if username > node.username {
                current = &mut node.right;
            } else {
                // User already exists, just update the ID
                node.id = id;
                return;
            }
        }

        // We've reached an empty spot, insert the new node here
        *current = Some(Box::new(Node {
            username,
            id,
            left: None,
            right: None,
        }));
    }
}

Finding a User in the Tree

Searching is where the BST really shines. Instead of checking every single user, we can discard half the remaining tree with every step. I'll implement this using a recursive approach this time, just to show you how it differs from the iterative insertion we just did.

impl UserRegistry {
    pub fn get(&self, username: &str) -> Option<u32> {
        fn search(node: &Option<Box<Node>>, target: &str) -> Option<u32> {
            match node {
                None => None,
                Some(n) if n.username == target => Some(n.id),
                Some(n) if target < n.username.as_str() => search(&n.left, target),
                Some(n) => search(&n.right, target),
            }
        }
        search(&self.root, username)
    }
}

Notice how we're passing &Option<Box<Node>> into the helper. We aren't taking ownership of the nodes; we're just borrowing them as we dive deeper into the tree. If we tried to move the node out of the Option, the compiler would stop us because we don't own the tree—we're just searching it.

📋 Practical Task

Exercise: Implement an "In-Order Traversal" for UserRegistry

A major advantage of a BST is that if you visit the nodes in a specific order (Left, Root, Right), you get all the elements sorted alphabetically.

Your task is to add a method to the UserRegistry called list_users. This method should:

1. Traverse the tree in-order.
2. Collect the usernames and IDs into a Vec<(String, u32)>.
3. Return that vector to the caller.

You will likely need a private recursive helper function to handle the traversal, as you did with the search logic in the lesson. Ensure that you are borrowing the nodes, not moving them!