1001 Advanced

Binary Tree — Size, Membership, Traversal

Functional Programming

Tutorial

The Problem

Implement core operations on a binary tree: count nodes, measure depth, check membership, and produce a preorder traversal. The tree is a recursive algebraic data type with no balancing invariants.

🎯 Learning Outcomes

• How to define recursive algebraic data types in Rust using enums with Box for heap allocation

• Implement structural recursion on trees using match — the direct equivalent of OCaml's pattern matching

• Build a linear-time traversal using a mutable accumulator to avoid quadratic list concatenation

Code Example

#![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 ()

Key Differences

Heap allocation: Rust requires Box for recursive enum variants; OCaml heap-allocates automatically

Accumulator style: OCaml threads the accumulator as a function parameter returning a new list; Rust passes &mut Vec avoiding allocation overhead

Membership: Both use short-circuit ||; OCaml's polymorphic = works on any type, while Rust requires the PartialEq bound

OCaml Approach

OCaml defines the same type with variant constructors and implements all operations as let rec functions using function pattern matching. The preorder accumulator uses list prepending (v :: go (go acc r) l) to build the result without intermediate allocations.

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]);
    }
}

Exercises

Add an inorder traversal and verify it produces a sorted sequence when the tree is a binary search tree

Implement height (same as depth) and is_balanced — a tree is balanced if the depths of its two subtrees differ by at most 1 at every node

Implement map_tree that transforms every node value with a function f: T -> U, returning a Tree<U> of the same shape

Open Source Repos

functional-rust

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

Rust