ExamplesBy LevelBy TopicLearning Paths
061 Intermediate
← 060062 →

061 — Binary Tree (Size, Membership, Traversal)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "061 — Binary Tree (Size, Membership, Traversal)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. This example implements a generic binary tree with the core operations from OCaml's CS3110 course: size, depth, membership, and traversal. Key difference from OCaml: 1. **`Box` for recursion**: Rust requires `Box<Tree<T>>` in Node. OCaml allocates all heap values uniformly — no explicit boxing.

Tutorial

The Problem

This example implements a generic binary tree with the core operations from OCaml's CS3110 course: size, depth, membership, and traversal. Unlike the 99 Problems tree (examples 029-040) which focuses on structural puzzles, this tree is a programming exercise in generics and trait bounds — the foundation for building a binary search tree (BST).

Binary trees are the basis for BSTs (BTreeMap, BTreeSet), heaps (BinaryHeap), Huffman coding, and expression trees in compilers. Understanding the generic Tree<T> with trait bounds (PartialEq for mem, Ord for BST) is prerequisite for implementing any tree-based data structure.

🎯 Learning Outcomes

  • • Define Tree<T> as a generic recursive enum with Box for heap allocation
  • • Use T: PartialEq as a trait bound for membership testing
  • • Implement size, depth, mem, and in/pre/post-order traversal
  • • Use helper constructors to avoid repeated Box::new at call sites
  • • Recognize how the tree structure shapes the recursive function structure
  • • Define Tree<T> with Box<Tree<T>> subtrees and implement size, depth, and mem operations
  • • Use T: PartialEq as a trait bound only on mem — leave other operations without bounds when they don't need comparison

    • Code Example

    #![allow(clippy::all)]
/// Binary Tree — Size, Membership, Traversal
///
/// A recursive enum mirrors OCaml's algebraic data type for binary trees.
/// Rust's `enum` is the direct equivalent of OCaml's `type 'a tree = Leaf | Node of ...`.
/// Key difference: Rust requires `Box` for recursive types because it needs to know
/// the size at compile time — OCaml's GC handles this transparently.

/// A generic binary tree. `Box` is needed because recursive types
/// would otherwise have infinite size on the stack.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    /// Helper to construct a node without writing Box::new everywhere.
    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }

    /// Helper to construct a leaf.
    pub fn leaf() -> Self {
        Tree::Leaf
    }
}

/// Count the number of nodes (recursive, mirrors OCaml's `size`).
pub fn size<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + size(l) + size(r),
    }
}

/// Compute the depth (height) of the tree.
pub fn depth<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + depth(l).max(depth(r)),
    }
}

/// Check membership — requires `PartialEq` for comparison.
/// In OCaml, structural equality is built in; in Rust we use trait bounds.
pub fn mem<T: PartialEq>(x: &T, tree: &Tree<T>) -> bool {
    match tree {
        Tree::Leaf => false,
        Tree::Node(v, l, r) => v == x || mem(x, l) || mem(x, r),
    }
}

/// Preorder traversal using an accumulator (tail-recursive style).
/// Returns owned values — requires `Clone` since we borrow the tree.
pub fn preorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    fn go<T: Clone>(tree: &Tree<T>, acc: &mut Vec<T>) {
        match tree {
            Tree::Leaf => {}
            Tree::Node(v, l, r) => {
                acc.push(v.clone());
                go(l, acc);
                go(r, acc);
            }
        }
    }
    let mut result = Vec::new();
    go(tree, &mut result);
    result
}

/// Inorder traversal — iterative with explicit stack, zero cloning needed
/// if we only collect references.
pub fn inorder<T>(tree: &Tree<T>) -> Vec<&T> {
    let mut result = Vec::new();
    let mut stack: Vec<&Tree<T>> = Vec::new();
    let mut current = tree;
    loop {
        match current {
            Tree::Node(v, l, _r) => {
                stack.push(current);
                current = l;
            }
            Tree::Leaf => {
                if let Some(node) = stack.pop() {
                    if let Tree::Node(v, _, r) = node {
                        result.push(v);
                        current = r;
                    }
                } else {
                    break;
                }
            }
        }
    }
    result
}

#[cfg(test)]
mod tests {
    use super::*;
    use Tree::*;

    fn sample_tree() -> Tree<i32> {
        //      4
        //     / \
        //    2   5
        //   / \
        //  1   3
        Tree::node(
            4,
            Tree::node(2, Tree::node(1, Leaf, Leaf), Tree::node(3, Leaf, Leaf)),
            Tree::node(5, Leaf, Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample_tree()), 5);
        assert_eq!(size::<i32>(&Leaf), 0);
        assert_eq!(size(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_depth() {
        assert_eq!(depth(&sample_tree()), 3);
        assert_eq!(depth::<i32>(&Leaf), 0);
        assert_eq!(depth(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_mem() {
        let t = sample_tree();
        assert!(mem(&3, &t));
        assert!(mem(&4, &t));
        assert!(!mem(&99, &t));
        assert!(!mem::<i32>(&1, &Leaf));
    }

    #[test]
    fn test_preorder() {
        assert_eq!(preorder(&sample_tree()), vec![4, 2, 1, 3, 5]);
        assert_eq!(preorder::<i32>(&Leaf), vec![]);
    }

    #[test]
    fn test_inorder() {
        assert_eq!(inorder(&sample_tree()), vec![&1, &2, &3, &4, &5]);
        assert_eq!(inorder::<i32>(&Leaf), Vec::<&i32>::new());
    }

    #[test]
    fn test_single_node() {
        let t = Tree::node(42, Leaf, Leaf);
        assert_eq!(size(&t), 1);
        assert_eq!(depth(&t), 1);
        assert!(mem(&42, &t));
        assert_eq!(preorder(&t), vec![42]);
    }
}

    Key Differences

  • **Box for recursion**: Rust requires Box<Tree<T>> in Node. OCaml allocates all heap values uniformly — no explicit boxing.
  • Trait bounds: Rust requires explicit T: PartialEq for mem. OCaml's structural equality works on all types automatically.
  • Helper constructors: Rust's Tree::node(v, l, r) hides Box::new. OCaml: Node (v, l, r) is direct.
  • Derive macros: Rust can #[derive(Debug, Clone, PartialEq)] on Tree. OCaml's structural equality and printing work automatically.
  • **Generic T with trait bounds:** Tree<T> where T: PartialEq for membership. The bound is required only for mem — other operations don't need it. Rust's monomorphization generates separate code for each concrete T.
  • **Box<Tree<T>> overhead:** Each heap allocation (one per node) has overhead. For performance-critical trees, arena allocation (typed-arena crate) or Vec-based trees are more efficient.
  • OCaml's polymorphic equality: OCaml's (=) works on any type for structural equality — no trait bound needed. Rust requires explicit PartialEq because the compiler doesn't know if two values of type T can be compared.
  • **size vs len:** Trees use size() or count() for node count. Rust's built-in collections use len(). The naming convention helps distinguish data structure operations from collection operations.

    • OCaml Approach

    OCaml's CS3110 tree: type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree. Operations: let rec size = function Leaf -> 0 | Node (_, l, r) -> 1 + size l + size r. Membership: let rec mem x = function Leaf -> false | Node (v, l, r) -> v = x || mem x l || mem x r. No boxing needed — OCaml's GC handles heap allocation for recursive types.

    Full Source

    #![allow(clippy::all)]
/// Binary Tree — Size, Membership, Traversal
///
/// A recursive enum mirrors OCaml's algebraic data type for binary trees.
/// Rust's `enum` is the direct equivalent of OCaml's `type 'a tree = Leaf | Node of ...`.
/// Key difference: Rust requires `Box` for recursive types because it needs to know
/// the size at compile time — OCaml's GC handles this transparently.

/// A generic binary tree. `Box` is needed because recursive types
/// would otherwise have infinite size on the stack.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    /// Helper to construct a node without writing Box::new everywhere.
    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }

    /// Helper to construct a leaf.
    pub fn leaf() -> Self {
        Tree::Leaf
    }
}

/// Count the number of nodes (recursive, mirrors OCaml's `size`).
pub fn size<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + size(l) + size(r),
    }
}

/// Compute the depth (height) of the tree.
pub fn depth<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + depth(l).max(depth(r)),
    }
}

/// Check membership — requires `PartialEq` for comparison.
/// In OCaml, structural equality is built in; in Rust we use trait bounds.
pub fn mem<T: PartialEq>(x: &T, tree: &Tree<T>) -> bool {
    match tree {
        Tree::Leaf => false,
        Tree::Node(v, l, r) => v == x || mem(x, l) || mem(x, r),
    }
}

/// Preorder traversal using an accumulator (tail-recursive style).
/// Returns owned values — requires `Clone` since we borrow the tree.
pub fn preorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    fn go<T: Clone>(tree: &Tree<T>, acc: &mut Vec<T>) {
        match tree {
            Tree::Leaf => {}
            Tree::Node(v, l, r) => {
                acc.push(v.clone());
                go(l, acc);
                go(r, acc);
            }
        }
    }
    let mut result = Vec::new();
    go(tree, &mut result);
    result
}

/// Inorder traversal — iterative with explicit stack, zero cloning needed
/// if we only collect references.
pub fn inorder<T>(tree: &Tree<T>) -> Vec<&T> {
    let mut result = Vec::new();
    let mut stack: Vec<&Tree<T>> = Vec::new();
    let mut current = tree;
    loop {
        match current {
            Tree::Node(v, l, _r) => {
                stack.push(current);
                current = l;
            }
            Tree::Leaf => {
                if let Some(node) = stack.pop() {
                    if let Tree::Node(v, _, r) = node {
                        result.push(v);
                        current = r;
                    }
                } else {
                    break;
                }
            }
        }
    }
    result
}

#[cfg(test)]
mod tests {
    use super::*;
    use Tree::*;

    fn sample_tree() -> Tree<i32> {
        //      4
        //     / \
        //    2   5
        //   / \
        //  1   3
        Tree::node(
            4,
            Tree::node(2, Tree::node(1, Leaf, Leaf), Tree::node(3, Leaf, Leaf)),
            Tree::node(5, Leaf, Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample_tree()), 5);
        assert_eq!(size::<i32>(&Leaf), 0);
        assert_eq!(size(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_depth() {
        assert_eq!(depth(&sample_tree()), 3);
        assert_eq!(depth::<i32>(&Leaf), 0);
        assert_eq!(depth(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_mem() {
        let t = sample_tree();
        assert!(mem(&3, &t));
        assert!(mem(&4, &t));
        assert!(!mem(&99, &t));
        assert!(!mem::<i32>(&1, &Leaf));
    }

    #[test]
    fn test_preorder() {
        assert_eq!(preorder(&sample_tree()), vec![4, 2, 1, 3, 5]);
        assert_eq!(preorder::<i32>(&Leaf), vec![]);
    }

    #[test]
    fn test_inorder() {
        assert_eq!(inorder(&sample_tree()), vec![&1, &2, &3, &4, &5]);
        assert_eq!(inorder::<i32>(&Leaf), Vec::<&i32>::new());
    }

    #[test]
    fn test_single_node() {
        let t = Tree::node(42, Leaf, Leaf);
        assert_eq!(size(&t), 1);
        assert_eq!(depth(&t), 1);
        assert!(mem(&42, &t));
        assert_eq!(preorder(&t), vec![42]);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;
    use Tree::*;

    fn sample_tree() -> Tree<i32> {
        //      4
        //     / \
        //    2   5
        //   / \
        //  1   3
        Tree::node(
            4,
            Tree::node(2, Tree::node(1, Leaf, Leaf), Tree::node(3, Leaf, Leaf)),
            Tree::node(5, Leaf, Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample_tree()), 5);
        assert_eq!(size::<i32>(&Leaf), 0);
        assert_eq!(size(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_depth() {
        assert_eq!(depth(&sample_tree()), 3);
        assert_eq!(depth::<i32>(&Leaf), 0);
        assert_eq!(depth(&Tree::node(1, Leaf, Leaf)), 1);
    }

    #[test]
    fn test_mem() {
        let t = sample_tree();
        assert!(mem(&3, &t));
        assert!(mem(&4, &t));
        assert!(!mem(&99, &t));
        assert!(!mem::<i32>(&1, &Leaf));
    }

    #[test]
    fn test_preorder() {
        assert_eq!(preorder(&sample_tree()), vec![4, 2, 1, 3, 5]);
        assert_eq!(preorder::<i32>(&Leaf), vec![]);
    }

    #[test]
    fn test_inorder() {
        assert_eq!(inorder(&sample_tree()), vec![&1, &2, &3, &4, &5]);
        assert_eq!(inorder::<i32>(&Leaf), Vec::<&i32>::new());
    }

    #[test]
    fn test_single_node() {
        let t = Tree::node(42, Leaf, Leaf);
        assert_eq!(size(&t), 1);
        assert_eq!(depth(&t), 1);
        assert!(mem(&42, &t));
        assert_eq!(preorder(&t), vec![42]);
    }
}

    Deep Comparison

    Binary Tree — Size, Membership, Traversal: OCaml vs Rust

    The Core Insight

    Binary trees are the canonical recursive data structure. Both languages use algebraic types (OCaml's type / Rust's enum), but Rust's ownership model forces you to think about where tree nodes live in memory — a distinction OCaml's garbage collector hides entirely.

    OCaml Approach

    OCaml's type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree is beautifully concise. The GC handles all allocation and deallocation, so recursive types "just work" without any indirection markers. Pattern matching with function keyword makes structural recursion read almost like a mathematical definition. Polymorphism comes free via 'a type parameters, and structural equality (=) works on any type without extra annotations.

    Rust Approach

    Rust's enum Tree<T> { Leaf, Node(T, Box<Tree<T>>, Box<Tree<T>>) } requires Box for heap allocation of recursive children — without it, the compiler can't compute the enum's size. This is the key tradeoff: explicit memory layout in exchange for zero-cost abstractions and no GC pauses. Generic functions need trait bounds (PartialEq for comparison, Clone for copying values out of borrowed trees). The &Tree<T> borrow pattern lets traversals share data without cloning.

    Side-by-Side

    ConceptOCamlRust
    MemoryGC-managed, implicit indirectionBox<T> for explicit heap allocation
    Recursive typesDirect, no annotation neededRequires Box to break infinite size
    EqualityStructural = on any typeRequires PartialEq trait bound
    Polymorphism'a type parameter<T> generic with trait bounds
    TraversalReturns new list, GC cleans upBorrows with &T or clones with Clone
    Pattern matchingfunction keyword sugarmatch expression

    What Rust Learners Should Notice

  • • Box<T> is Rust's way of saying "this value lives on the heap" — it's a single-owner smart pointer, not a shared reference
  • • You must choose: return Vec<&T> (borrowing) or Vec<T> (cloning/moving). OCaml doesn't force this choice because GC manages lifetimes
  • • Helper constructors like Tree::node() reduce Box::new() noise — a common Rust pattern for recursive types
  • • The #[derive(Debug, Clone, PartialEq)] line is Rust's way of opting into capabilities that OCaml provides by default
  • • Iterative traversal with an explicit stack avoids deep recursion stack overflow — important in Rust where stack size is bounded

    • Further Reading

  • • [The Rust Book — Enums](https://doc.rust-lang.org/book/ch06-01-defining-an-enum.html)
  • • [The Rust Book — Box<T>](https://doc.rust-lang.org/book/ch15-01-box.html)
  • • [OCaml Trees](https://cs3110.github.io/textbook/chapters/data/trees.html)

    • Exercises

  • BST operations: Add insert(x: T, tree: Tree<T>) -> Tree<T> and search(x: &T, tree: &Tree<T>) -> bool for a BST (requiring T: Ord). Maintain the BST invariant: left < root < right.
  • Level-order: Write level_order(tree: &Tree<T>) -> Vec<Vec<T>> using a queue-based BFS. Compare output with preorder and inorder.
  • To sorted vec: Write to_sorted_vec<T: Ord + Clone>(tree: &Tree<T>) -> Vec<T> by inorder traversal of a BST. Verify it produces a sorted sequence.
  • BST insert: Implement insert<T: Ord>(tree: Tree<T>, value: T) -> Tree<T> that inserts a value into a binary search tree, maintaining the BST ordering invariant.
  • **Tree equality with PartialEq**: Implement PartialEq for Tree<T> where T: PartialEq and write tests verifying t == t (reflexivity), t1 == t2 => t2 == t1 (symmetry), and t1 == t2 && t2 == t3 => t1 == t3 (transitivity).

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust