031 Intermediate GitHub

031 — Collect the Leaves of a Binary Tree in a List

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "031 — Collect the Leaves of a Binary Tree in a List" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Collecting all leaf values into a list (OCaml 99 Problems #31) extends the leaf-counting pattern: instead of incrementing a counter, we collect the actual values. Key difference from OCaml: 1. **Value at leaves**: In our `Tree<T>` type, the value is at `Node`, not at `Leaf`. OCaml 99 Problems uses the same type: value is at `Node`. "Leaf nodes" are `Node(x, Leaf, Leaf)` — nodes with two null children.

Tutorial

The Problem

Collecting all leaf values into a list (OCaml 99 Problems #31) extends the leaf-counting pattern: instead of incrementing a counter, we collect the actual values. This is the leaf traversal — the first step in algorithms like Huffman decoding, expression evaluation (leaves are operands), and tree serialization.

The problem introduces a key pattern in functional tree processing: building a result list by appending contributions from left and right subtrees. The naive approach using @ (OCaml) or extend (Rust) is O(n·d) where d is depth. The efficient approach uses an accumulator or difference lists to achieve O(n).

🎯 Learning Outcomes

• Collect values from tree leaves using structural recursion

• Return values in left-to-right order (inorder leaf traversal)

• Use extend to combine results from left and right subtrees

• Understand the efficiency difference between appending and accumulator-based collection

• Recognize that leaf collection is a degenerate form of tree flattening

• Collect leaf values in left-to-right order using recursive extend — processing left subtree before right subtree

• For large trees, use accumulator style (push directly to &mut Vec) to avoid O(n*depth) extend overhead

Code Example

#![allow(clippy::all)]
// Collect the values of leaf nodes — Node(x, Leaf, Leaf) — left to right (OCaml 99 Problems #31).
#[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 collect_leaves<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, l, r) if matches!(**l, Tree::Leaf) && matches!(**r, Tree::Leaf) => {
            vec![v.clone()]
        }
        Tree::Node(_, l, r) => {
            let mut left_leaves = collect_leaves(l);
            left_leaves.extend(collect_leaves(r));
            left_leaves
        }
    }
}

#[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_collect_leaves_left_to_right() {
        assert_eq!(collect_leaves(&sample()), vec![2, 4]);
    }

    #[test]
    fn test_single_node_is_its_own_leaf() {
        assert_eq!(collect_leaves(&Tree::node(9, Tree::leaf(), Tree::leaf())), vec![9]);
    }

    #[test]
    fn test_empty_tree_has_no_leaves() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_leaves::<i32>(&Tree::leaf()), empty);
    }
}

(* Collect Leaves *)
(* OCaml 99 Problems #31 *)

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 collect_leaves = function
  | Leaf -> []
  | Node (x, Leaf, Leaf) -> [x]
  | Node (_, l, r) -> collect_leaves l @ collect_leaves r

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (collect_leaves sample = [2; 4]);
  assert (collect_leaves (node 9 leaf leaf) = [9]);
  assert (collect_leaves leaf = []);
  print_endline "✓ OCaml tests passed"

Key Differences

Value at leaves: In our Tree<T> type, the value is at Node, not at Leaf. OCaml 99 Problems uses the same type: value is at Node. "Leaf nodes" are Node(x, Leaf, Leaf) — nodes with two null children.

**@ vs extend**: OCaml's leaves l @ leaves r copies the left result — O(|left|). Rust's approach of extending a mutable Vec is O(|right|). Both are O(n) total.

Accumulator efficiency: OCaml's accumulator version leaves_acc (leaves_acc acc r) l processes right then left, building in reverse. Pass List.rev at the end or process left then right.

Difference lists: For maximum efficiency when collecting from many nodes, use difference lists (example 081) or Rust's Vec::extend which is amortized O(1) per element.

**extend vs append cost:** Rust's result.extend(leaves(left)) copies elements from the left result into the output. OCaml's @ also copies. For deep trees, accumulator style is O(n) vs O(n·d) for extend/append.

Left-to-right order: Both implementations produce leaves in left-to-right order (in-order traversal restricted to leaf nodes). This is the natural order for reading leaf values.

**Vec capacity hint:** Vec::with_capacity(count_leaves(tree)) pre-allocates the output, avoiding reallocations during traversal.

OCaml Approach

OCaml's version: let rec leaves = function | Leaf -> [] | Node (x, Leaf, Leaf) -> [x] | Node (_, l, r) -> leaves l @ leaves r. The middle case identifies a node with two leaf children (a proper leaf node in a "full" tree where only leaf nodes carry values). The @ concatenation builds the list. For efficiency, use accumulator style: let rec leaves_acc acc = function | Leaf -> acc | Node (x, Leaf, Leaf) -> x :: acc | Node (_, l, r) -> leaves_acc (leaves_acc acc r) l.

OCaml: let rec leaves = function | Leaf -> [] | Node (_, Leaf, Leaf) -> [?] (* depends on tree definition *) | Node (_, l, r) -> leaves l @ leaves r. The @ append is O(|left result|), making the naive version O(n·d) where d is depth. The efficient version: let rec leaves_aux acc = function | Leaf -> acc | Node (v, Leaf, Leaf) -> v :: acc | Node (_, l, r) -> leaves_aux (leaves_aux acc r) l uses an accumulator and processes right-to-left for correct left-to-right order.

Full Source

#![allow(clippy::all)]
// Collect the values of leaf nodes — Node(x, Leaf, Leaf) — left to right (OCaml 99 Problems #31).
#[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 collect_leaves<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(v, l, r) if matches!(**l, Tree::Leaf) && matches!(**r, Tree::Leaf) => {
            vec![v.clone()]
        }
        Tree::Node(_, l, r) => {
            let mut left_leaves = collect_leaves(l);
            left_leaves.extend(collect_leaves(r));
            left_leaves
        }
    }
}

#[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_collect_leaves_left_to_right() {
        assert_eq!(collect_leaves(&sample()), vec![2, 4]);
    }

    #[test]
    fn test_single_node_is_its_own_leaf() {
        assert_eq!(collect_leaves(&Tree::node(9, Tree::leaf(), Tree::leaf())), vec![9]);
    }

    #[test]
    fn test_empty_tree_has_no_leaves() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_leaves::<i32>(&Tree::leaf()), empty);
    }
}

(* Collect Leaves *)
(* OCaml 99 Problems #31 *)

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 collect_leaves = function
  | Leaf -> []
  | Node (x, Leaf, Leaf) -> [x]
  | Node (_, l, r) -> collect_leaves l @ collect_leaves r

(* Tests *)
let () =
  let sample = node 1 (node 2 leaf leaf) (node 3 (node 4 leaf leaf) leaf) in
  assert (collect_leaves sample = [2; 4]);
  assert (collect_leaves (node 9 leaf leaf) = [9]);
  assert (collect_leaves leaf = []);
  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_collect_leaves_left_to_right() {
        assert_eq!(collect_leaves(&sample()), vec![2, 4]);
    }

    #[test]
    fn test_single_node_is_its_own_leaf() {
        assert_eq!(collect_leaves(&Tree::node(9, Tree::leaf(), Tree::leaf())), vec![9]);
    }

    #[test]
    fn test_empty_tree_has_no_leaves() {
        let empty: Vec<i32> = vec![];
        assert_eq!(collect_leaves::<i32>(&Tree::leaf()), empty);
    }
}

Deep Comparison

OCaml vs Rust: Collect Leaves

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

Internal nodes: Write internal_nodes<T: Clone>(tree: &Tree<T>) -> Vec<T> that collects values from nodes that are not leaves (nodes with at least one non-Leaf child).

Nodes at depth: Write at_depth<T: Clone>(tree: &Tree<T>, d: usize) -> Vec<T> that collects all node values at exactly depth d (root is depth 0).

Fringe equality: Two trees have the same fringe if they have the same sequence of leaf values. Write same_fringe<T: Clone + PartialEq>(t1: &Tree<T>, t2: &Tree<T>) -> bool. Can you do it without materializing both fringes?

Accumulator style: Rewrite collect_leaves to use collect_leaves_aux(tree: &Tree<T>, acc: &mut Vec<T>) — pushing values directly into a mutable accumulator. Compare performance with the return-value version for large trees.

Leaf paths: Implement leaf_paths<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> that returns all root-to-leaf paths as vectors of node values.

Open Source Repos

functional-rust

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

Rust