1001 Advanced

Binary Tree — Size, Membership, Traversal

Functional Programming

Tutorial

The Problem

Implement four core operations on an unbalanced binary tree: count the number of nodes (size), measure the longest root-to-leaf path (depth), check whether a value is stored anywhere in the tree (mem), and produce a preorder traversal as a flat list. The tree carries no balancing or ordering invariants — it is a pure recursive algebraic data type used to practice structural recursion. Mastering these operations is the prerequisite for every more advanced tree algorithm.

🎯 Learning Outcomes

• How to define a recursive algebraic data type in Rust as an enum whose recursive variants require Box for heap allocation

• How Rust's match on an enum directly mirrors OCaml's function pattern matching over variant constructors

• Why Box<Tree<T>> is necessary in Rust while OCaml heap-allocates recursive types automatically

• How to write a linear-time traversal using a &mut Vec<T> accumulator rather than returning and concatenating intermediate lists

• Why the PartialEq trait bound on mem is the Rust equivalent of OCaml's polymorphic structural equality =

Code Example

#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T: PartialEq> Tree<T> {
    pub fn size(&self) -> usize {
        match self {
            Tree::Leaf => 0,
            Tree::Node(_, l, r) => 1 + l.size() + r.size(),
        }
    }

    pub fn mem(&self, x: &T) -> bool {
        match self {
            Tree::Leaf => false,
            Tree::Node(v, l, r) => v == x || l.mem(x) || r.mem(x),
        }
    }
}

type 'a tree =
  | Leaf
  | Node of 'a * 'a tree * 'a tree

let rec size = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + size l + size r

let rec depth = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + max (depth l) (depth r)

let rec mem x = function
  | Leaf           -> false
  | Node (v, l, r) -> v = x || mem x l || mem x r

(* Linear-time preorder using accumulator trick *)
let preorder t =
  let rec go acc = function
    | Leaf           -> acc
    | Node (v, l, r) -> v :: go (go acc r) l
  in go [] t

Key Differences

Heap allocation: Rust requires explicit Box<Tree<T>> to make the recursive enum representable; OCaml allocates all heap values automatically through its runtime

Trait bounds: Rust's mem requires T: PartialEq to compare values; OCaml's polymorphic = works on any type at runtime without static annotation

Accumulator style: OCaml threads the accumulator as a function parameter and returns a new list; Rust passes &mut Vec so the helper mutates in place — same asymptotic cost, different ownership expression

Traversal direction: OCaml's accumulator preorder builds in reverse (v :: go (go acc r) l); Rust's mutable-push version visits naturally left-to-right — both are O(n) but the ownership model shapes the implementation choice

OCaml Approach

OCaml defines type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree and implements each operation as a let rec function using function for pattern matching. size, depth, and mem are textbook structural recursions. The preorder function uses an accumulator (let rec go acc = function | Leaf -> acc | Node(v,l,r) -> v :: go (go acc r) l) to avoid quadratic list concatenation: by reversing the traversal direction in the accumulator, it builds the result in a single linear pass. OCaml's garbage collector handles all heap allocation invisibly.

Full Source

#![allow(clippy::all)]
//! Binary Tree — Size, Membership, Traversal
//! See example.ml for OCaml reference

#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T: PartialEq> Tree<T> {
    /// Number of nodes in the tree.
    pub fn size(&self) -> usize {
        match self {
            Tree::Leaf => 0,
            Tree::Node(_, l, r) => 1 + l.size() + r.size(),
        }
    }

    /// Height of the tree (number of edges on longest root-to-leaf path).
    pub fn depth(&self) -> usize {
        match self {
            Tree::Leaf => 0,
            Tree::Node(_, l, r) => 1 + l.depth().max(r.depth()),
        }
    }

    /// Returns true if `x` is stored anywhere in the tree.
    pub fn mem(&self, x: &T) -> bool {
        match self {
            Tree::Leaf => false,
            Tree::Node(v, l, r) => v == x || l.mem(x) || r.mem(x),
        }
    }
}

/// Preorder traversal (root, left, right) using a mutable accumulator — linear time.
/// Mirrors OCaml's `let rec go acc = function | Leaf -> acc | Node(v,l,r) -> v :: go (go acc r) l`.
pub fn preorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    fn go<T: Clone>(tree: &Tree<T>, acc: &mut Vec<T>) {
        if let Tree::Node(v, l, r) = tree {
            acc.push(v.clone());
            go(l, acc);
            go(r, acc);
        }
    }
    let mut result = Vec::new();
    go(tree, &mut result);
    result
}

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

    //      4
    //     / \
    //    2   5
    //   / \
    //  1   3
    fn sample() -> Tree<i32> {
        Node(
            4,
            Box::new(Node(
                2,
                Box::new(Node(1, Box::new(Leaf), Box::new(Leaf))),
                Box::new(Node(3, Box::new(Leaf), Box::new(Leaf))),
            )),
            Box::new(Node(5, Box::new(Leaf), Box::new(Leaf))),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(sample().size(), 5);
        assert_eq!(Leaf::<i32>.size(), 0);
    }

    #[test]
    fn test_depth() {
        assert_eq!(sample().depth(), 3);
        assert_eq!(Leaf::<i32>.depth(), 0);
    }

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

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

    #[test]
    fn test_single_node() {
        let t: Tree<i32> = Node(42, Box::new(Leaf), Box::new(Leaf));
        assert_eq!(t.size(), 1);
        assert_eq!(t.depth(), 1);
        assert!(t.mem(&42));
        assert_eq!(preorder(&t), vec![42]);
    }
}

type 'a tree =
  | Leaf
  | Node of 'a * 'a tree * 'a tree

let rec size = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + size l + size r

let rec depth = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + max (depth l) (depth r)

let rec mem x = function
  | Leaf           -> false
  | Node (v, l, r) -> v = x || mem x l || mem x r

(* Linear-time preorder using accumulator *)
let preorder t =
  let rec go acc = function
    | Leaf           -> acc
    | Node (v, l, r) -> v :: go (go acc r) l
  in go [] t

(*      4
       / \
      2   5
     / \
    1   3   *)
let t = Node (4, Node (2, Node (1, Leaf, Leaf), Node (3, Leaf, Leaf)), Node (5, Leaf, Leaf))

let () =
  Printf.printf "size     = %d\n" (size t);
  Printf.printf "depth    = %d\n" (depth t);
  Printf.printf "mem 3    = %b\n" (mem 3 t);
  Printf.printf "mem 99   = %b\n" (mem 99 t);
  Printf.printf "preorder = ";
  List.iter (Printf.printf "%d ") (preorder t);
  print_newline ()

✓ Tests Rust test suite

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

    //      4
    //     / \
    //    2   5
    //   / \
    //  1   3
    fn sample() -> Tree<i32> {
        Node(
            4,
            Box::new(Node(
                2,
                Box::new(Node(1, Box::new(Leaf), Box::new(Leaf))),
                Box::new(Node(3, Box::new(Leaf), Box::new(Leaf))),
            )),
            Box::new(Node(5, Box::new(Leaf), Box::new(Leaf))),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(sample().size(), 5);
        assert_eq!(Leaf::<i32>.size(), 0);
    }

    #[test]
    fn test_depth() {
        assert_eq!(sample().depth(), 3);
        assert_eq!(Leaf::<i32>.depth(), 0);
    }

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

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

    #[test]
    fn test_single_node() {
        let t: Tree<i32> = Node(42, Box::new(Leaf), Box::new(Leaf));
        assert_eq!(t.size(), 1);
        assert_eq!(t.depth(), 1);
        assert!(t.mem(&42));
        assert_eq!(preorder(&t), vec![42]);
    }
}

Deep Comparison

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

Side-by-Side Code

OCaml

type 'a tree =
  | Leaf
  | Node of 'a * 'a tree * 'a tree

let rec size = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + size l + size r

let rec depth = function
  | Leaf           -> 0
  | Node (_, l, r) -> 1 + max (depth l) (depth r)

let rec mem x = function
  | Leaf           -> false
  | Node (v, l, r) -> v = x || mem x l || mem x r

(* Linear-time preorder using accumulator trick *)
let preorder t =
  let rec go acc = function
    | Leaf           -> acc
    | Node (v, l, r) -> v :: go (go acc r) l
  in go [] t

Rust (idiomatic)

#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T: PartialEq> Tree<T> {
    pub fn size(&self) -> usize {
        match self {
            Tree::Leaf => 0,
            Tree::Node(_, l, r) => 1 + l.size() + r.size(),
        }
    }

    pub fn mem(&self, x: &T) -> bool {
        match self {
            Tree::Leaf => false,
            Tree::Node(v, l, r) => v == x || l.mem(x) || r.mem(x),
        }
    }
}

Rust (functional/recursive)

pub fn preorder<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    let mut result = Vec::new();
    preorder_go(tree, &mut result);
    result
}

fn preorder_go<T: Clone>(tree: &Tree<T>, acc: &mut Vec<T>) {
    if let Tree::Node(v, l, r) = tree {
        acc.push(v.clone());
        preorder_go(l, acc);
        preorder_go(r, acc);
    }
}

Type Signatures

Concept	OCaml	Rust
tree type	`type 'a tree = Leaf \\| Node of 'a * 'a tree * 'a tree`	`enum Tree<T> { Leaf, Node(T, Box<Tree<T>>, Box<Tree<T>>) }`
size	`val size : 'a tree -> int`	`fn size(&self) -> usize`
membership	`val mem : 'a -> 'a tree -> bool`	`fn mem(&self, x: &T) -> bool` (requires `T: PartialEq`)
preorder	`val preorder : 'a tree -> 'a list`	`fn preorder<T: Clone>(tree: &Tree<T>) -> Vec<T>`

Key Insights

Box for heap allocation: OCaml's runtime allocates all constructors on the heap automatically. Rust requires explicit Box<Tree<T>> inside the Node variant so the compiler can determine the enum's size at compile time — without Box, Tree<T> would be infinitely large.

Trait bounds at the use site: OCaml's polymorphic equality = works on any type at runtime. Rust's mem requires the explicit bound T: PartialEq — the compiler rejects the function without it. Bounds are declared where they are needed, not at the type definition.

Mutable accumulator vs. functional accumulator: OCaml's preorder uses the accumulator trick go (go acc r) l to achieve linear time without list concatenation. Rust uses a &mut Vec<T> shared across all recursive calls — semantically equivalent but expressed through mutable state rather than accumulator threading.

Pattern matching syntax: OCaml: function | Leaf -> ... | Node(v, l, r) -> .... Rust: match self { Tree::Leaf => ..., Tree::Node(v, l, r) => ... }. The structure is identical; Rust requires qualified variant names and explicit match.

Methods vs. free functions: OCaml defines size, depth, and mem as top-level functions taking the tree as the last argument. Rust groups them as inherent methods on impl<T: PartialEq> Tree<T>, called as tree.size() — idiomatic for a data structure's core operations.

When to Use Each Style

Use idiomatic Rust when: Implementing a data structure for a library — inherent methods on impl Tree<T> provide the cleanest API and integrate naturally with Rust's method call syntax. Use free functions when: The operation is generic over the tree type and does not belong to the tree itself (e.g., serialization, drawing), or when demonstrating the OCaml parallel explicitly.

Exercises

Add an inorder traversal method (left, root, right) and verify it produces a sorted sequence when the tree happens to be a valid binary search tree

Implement is_balanced — a tree is balanced if for every node the depth of the left and right subtrees differ by at most one; hint: write a helper that returns depth and balance simultaneously to avoid double traversal

Implement map_tree that applies a function f: Fn(T) -> U to every node value, returning a Tree<U> of the same shape, then verify preorder(map_tree(t, f)) == preorder(t).into_iter().map(f).collect()

Open Source Repos

functional-rust

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

Rust