031 — Collect the Leaves of a Binary Tree in a List
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
extend to combine results from left and right subtreesextend — processing left subtree before right subtreepush directly to &mut Vec) to avoid O(n*depth) extend overheadCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
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.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.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.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)]
// Placeholder — pending conversionDeep 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<T: Clone>(tree: &Tree<T>) -> Vec<T> that collects values from nodes that are not leaves (nodes with at least one non-Leaf child).at_depth<T: Clone>(tree: &Tree<T>, d: usize) -> Vec<T> that collects all node values at exactly depth d (root is depth 0).same_fringe<T: Clone + PartialEq>(t1: &Tree<T>, t2: &Tree<T>) -> bool. Can you do it without materializing both fringes?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<T: Clone>(tree: &Tree<T>) -> Vec<Vec<T>> that returns all root-to-leaf paths as vectors of node values.