🎓 A1Learner
🔍

Rust Binary Tree

A binary search tree is a branching structure where smaller values go left and larger values go right. Every step throws away half the tree, so searching stays fast.

A node and its two children

Option says a child may be missing. Box gives the recursive type a fixed size. It is the same trick as the linked list.

struct Node<T: Ord> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

Insert walks down to an empty slot

Smaller goes left, larger goes right, and an empty slot (None) is where the new node lands. Equal does nothing — this tree stores each value once.

Ordering::Less => insert_into(&mut node.left, value),
Ordering::Greater => insert_into(&mut node.right, value),
Ordering::Equal => {}

Each value lands once

Four inserts, three nodes: the second 3 walks down to the existing 3, sees Equal, and stops.

let mut tree = Tree::new();
tree.insert(5);
tree.insert(3);
tree.insert(8);
tree.insert(3);
println!("len = {}", tree.len());

Search follows the same path

has makes the same walk, but never looks at the subtrees it skips — that is why searching stays fast. len, by contrast, visits every node: 1 plus the counts of both sides.

Ordering::Less => search(&node.left, value),
Ordering::Greater => search(&node.right, value),
Ordering::Equal => true,

Example

use std::cmp::Ordering;
struct Node<T: Ord> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}
struct Tree<T: Ord> {
    root: Option<Box<Node<T>>>,
}
fn insert_into<T: Ord>(slot: &mut Option<Box<Node<T>>>, value: T) {
    match slot {
        None => *slot = Some(Box::new(Node { value, left: None, right: None })),
        Some(node) => match value.cmp(&node.value) {
            Ordering::Less => insert_into(&mut node.left, value),
            Ordering::Greater => insert_into(&mut node.right, value),
            Ordering::Equal => {}
        },
    }
}
fn search<T: Ord>(slot: &Option<Box<Node<T>>>, value: &T) -> bool {
    match slot {
        None => false,
        Some(node) => match value.cmp(&node.value) {
            Ordering::Less => search(&node.left, value),
            Ordering::Greater => search(&node.right, value),
            Ordering::Equal => true,
        },
    }
}
fn count<T: Ord>(slot: &Option<Box<Node<T>>>) -> usize {
    match slot {
        None => 0,
        Some(node) => 1 + count(&node.left) + count(&node.right),
    }
}
impl<T: Ord> Tree<T> {
    fn new() -> Tree<T> { Tree { root: None } }
    fn insert(&mut self, value: T) { insert_into(&mut self.root, value); }
    fn has(&self, value: &T) -> bool { search(&self.root, value) }
    fn len(&self) -> usize { count(&self.root) }
}
fn main() {
    let mut tree = Tree::new();
    for v in [5, 3, 8, 1, 4] { tree.insert(v); }
    tree.insert(3);
    println!("len = {}", tree.len());
    println!("has 4 = {}", tree.has(&4));
    println!("has 9 = {}", tree.has(&9));
}

Key points

  • Each node holds one value and two directions: left for smaller, right for larger.
  • The tree's shape depends on the order you insert.
  • Values arriving already sorted make a leaning line.
  • It looks like a linked list.
  • Building one here teaches how Box, Option and recursion work together.
  • A linked list is one long chain instead of a branching structure.

In this example, the tree starts empty, so its root is None. insert_into does the walking. On an empty slot it plants a fresh Node. On a filled slot it compares. Less walks left. Greater walks right. Equal does nothing. main inserts 5, 3, 8, 1 and 4. Then it inserts 3 a second time. The walk reaches the existing 3. It sees Equal and stops. So len counts 5, not 6. has uses the same walk as a search: 4 is found (true), 9 is not (false).

Note

Real programs usually take std's ready-made BTreeSet or BTreeMap, which keep themselves balanced.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Where does insert put a value that is smaller than the current node?