029 Intermediate GitHub

029 — Binary Tree (Algebraic Data Type)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "029 — Binary Tree (Algebraic Data Type)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. A binary tree is the most important recursive data structure in computer science. Key difference from OCaml: 1. **`Box` for recursion**: Rust needs `Box<Tree<T>>` because the compiler must compute the stack frame size. OCaml's uniform heap representation avoids this — all values are pointer

Tutorial

The Problem

A binary tree is the most important recursive data structure in computer science. It underlies binary search trees (std::collections::BTreeMap), heaps (priority queues), Huffman coding trees (compression), parse trees (compilers), and spatial partitioning (k-d trees, R-trees). The recursive definition — a tree is either a leaf or a node with a value and two subtrees — maps perfectly to algebraic data types.

OCaml 99 Problems #29 introduces the type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree as the central data type for problems 29-40. This is the canonical example of an algebraic data type (ADT), a sum type with two constructors. Understanding how to define and process ADTs is foundational to functional programming.

🎯 Learning Outcomes

• Define a generic recursive enum Tree<T> in Rust as the equivalent of OCaml's 'a tree

• Understand why Box is required for recursive enum variants in Rust

• Use Tree::node() and Tree::leaf() helper constructors for cleaner tree construction

• Implement basic operations: size, depth, membership via pattern matching

• Recognize how the tree structure mirrors the recursive function structure

• Define Tree<T> as a recursive enum using Box<Tree<T>> to break the otherwise infinite-size type

• Use node(v, l, r) and leaf() helper constructors to reduce Box::new boilerplate at construction sites

Code Example

#![allow(clippy::all)]
// Binary tree ADT (OCaml 99 Problems #29): the central recursive type for problems 29-40.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

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

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

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

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 4);
        assert_eq!(size::<i32>(&Tree::leaf()), 0);
    }

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

    #[test]
    fn test_mem() {
        assert!(mem(&sample(), &4));
        assert!(mem(&sample(), &1));
        assert!(!mem(&sample(), &5));
    }
}

(* Binary Tree *)
(* OCaml 99 Problems #29 *)

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

let node x l r = Node (x, l, r)
let leaf = Leaf

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

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (size sample = 4);
  assert (size leaf = 0);
  assert (depth sample = 3);
  assert (depth leaf = 0);
  assert (mem 4 sample = true);
  assert (mem 1 sample = true);
  assert (mem 5 sample = false);
  print_endline "✓ OCaml tests passed"

Key Differences

**Box for recursion**: Rust needs Box<Tree<T>> because the compiler must compute the stack frame size. OCaml's uniform heap representation avoids this — all values are pointer-sized.

Type parameter syntax: Rust: Tree<T>. OCaml: 'a tree. Both are parametric polymorphism; the syntax differs.

Helper constructors: Rust often defines fn node(val, left, right) to hide boxing. OCaml's Node (v, l, r) is direct — no hiding needed.

**PartialEq for mem**: Rust requires explicit T: PartialEq trait bound for value comparison. OCaml's structural equality works on all types automatically.

**Box<Tree<T>> for recursion:** Rust requires Box in recursive enum variants to give them a known size. OCaml's heap-allocated types need no annotation — the compiler handles it transparently.

GC vs ownership: OCaml's GC manages tree node lifetimes. Rust's ownership rules require the tree to be the sole owner of its subtrees — no shared references across the tree without Rc.

Constructor ergonomics: Box::new(Tree::Node(...)) is verbose in Rust. Helper constructors tree::node(v, l, r) hide this. OCaml's Node (x, l, r) is already concise.

Pattern matching depth: Both languages support nested pattern matching to arbitrary depth — matching Node(v, Node(_, _, _), Leaf) to detect a tree with a left child and no right child.

OCaml Approach

OCaml defines type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree. No boxing is needed because OCaml values are uniformly represented as tagged pointers on the heap — the GC handles recursive types automatically. Functions follow the same recursive structure: let rec size = function Leaf -> 0 | Node (_, l, r) -> 1 + size l + size r. The function keyword is shorthand for fun x -> match x with.

OCaml's tree type: type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree. This is the canonical definition used in all OCaml textbooks and the 99 Problems series. No annotation is needed for recursive types — OCaml's GC allocates nodes on the heap automatically. Helper: let node x l r = Node (x, l, r) and let leaf = Leaf.

Full Source

#![allow(clippy::all)]
// Binary tree ADT (OCaml 99 Problems #29): the central recursive type for problems 29-40.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

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

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

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

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 4);
        assert_eq!(size::<i32>(&Tree::leaf()), 0);
    }

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

    #[test]
    fn test_mem() {
        assert!(mem(&sample(), &4));
        assert!(mem(&sample(), &1));
        assert!(!mem(&sample(), &5));
    }
}

(* Binary Tree *)
(* OCaml 99 Problems #29 *)

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

let node x l r = Node (x, l, r)
let leaf = Leaf

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

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (size sample = 4);
  assert (size leaf = 0);
  assert (depth sample = 3);
  assert (depth leaf = 0);
  assert (mem 4 sample = true);
  assert (mem 1 sample = true);
  assert (mem 5 sample = false);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    fn sample() -> Tree<i32> {
        Tree::node(
            1,
            Tree::node(2, Tree::leaf(), Tree::leaf()),
            Tree::node(3, Tree::node(4, Tree::leaf(), Tree::leaf()), Tree::leaf()),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 4);
        assert_eq!(size::<i32>(&Tree::leaf()), 0);
    }

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

    #[test]
    fn test_mem() {
        assert!(mem(&sample(), &4));
        assert!(mem(&sample(), &1));
        assert!(!mem(&sample(), &5));
    }
}

Deep Comparison

OCaml vs Rust: Binary Tree

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Mirror: Write mirror(tree: Tree<T>) -> Tree<T> that swaps left and right children at every node. Verify that mirror(mirror(t)) == t.

Balanced: Write is_balanced<T>(tree: &Tree<T>) -> bool that returns true if no two leaves differ in depth by more than 1. Use depth from the implementation.

Path to node: Write path_to<T: PartialEq>(tree: &Tree<T>, target: &T) -> Option<Vec<bool>> that returns the path from root to the target (false = go left, true = go right), or None if not found.

Tree equality: Implement PartialEq for Tree<T> where T: PartialEq — two trees are equal if they have the same structure and values at every node. Write property tests to verify reflexivity, symmetry, and transitivity.

Mirror: Implement mirror(tree: Tree<T>) -> Tree<T> that swaps left and right subtrees at every level, producing the mirror image of the original tree.

Open Source Repos

functional-rust

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

Rust