030 — Count the Leaves of a Binary Tree
Tutorial Video
Text description (accessibility)
This video demonstrates the "030 — Count the Leaves of a Binary Tree" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Counting the leaves (nodes with no children) of a binary tree (OCaml 99 Problems #30) is a simple structural recursion exercise. Key difference from OCaml: 1. **Symmetric structure**: The Rust and OCaml implementations are nearly identical in structure — this is the point. Algebraic data types + pattern matching produce code whose shape mirrors the data.
Tutorial
The Problem
Counting the leaves (nodes with no children) of a binary tree (OCaml 99 Problems #30) is a simple structural recursion exercise. A leaf is a Leaf variant in our tree type. Counting leaves is useful in analyzing tree balance (more leaves = more complete), computing Huffman code lengths (each leaf is one codeword), and measuring the branching factor of search trees.
The problem introduces the pattern of accumulating a count by traversing an entire tree — the foundation for all tree analytics: depth, node count, sum of values, max value, and tree validation all use the same recursive traversal pattern.
🎯 Learning Outcomes
Tree<T> typeTree::Leaf) from internal nodes (Tree::Node)Leaf -> 1 and recursive case Node(_, l, r) -> count(l) + count(r)count_leaves + count_internal_nodes == total_node_count in testsCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
Leaf is a null node (no value). Some tree types define leaves as Node values with null children. The definition affects the count.count_leaves is a catamorphism — it replaces each constructor with a function. Leaf → 1, Node(_, l, r) → l_count + r_count. Example 080 generalizes this pattern.count_leaves_acc tree acc adds 1 for each Leaf. But Rust won't TCO this either way since the tree recursion is not tail-recursive.Tree<T> from example 029, a leaf node is one whose children are both Tree::Leaf. The Tree::Leaf variant itself has no value — it represents absence.count_leaves + count_internal_nodes = total_nodes. For a complete binary tree with n internal nodes, there are exactly n+1 leaves.OCaml Approach
OCaml's version: let rec count_leaves = function | Leaf -> 1 | Node (_, l, r) -> count_leaves l + count_leaves r. The pattern is identical — the function keyword matches directly on the tree. Leaf count is a classic example where the value at nodes is irrelevant, so it is bound to _.
OCaml: let rec count_leaves = function | Leaf -> 1 | Node (_, l, r) -> count_leaves l + count_leaves r. The leaf case returns 1 (a lone Leaf counts as a leaf). In OCaml 99 Problems, the tree has a different structure where Leaf carries no value, so a tree with a single value is Node(x, Leaf, Leaf) with two leaf children that are not counted as leaves in the same way. Clarify the definition for your specific tree type.
Full Source
#![allow(clippy::all)]
// Placeholder — pending conversionDeep Comparison
OCaml vs Rust: Count 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
count_nodes<T>(tree: &Tree<T>) -> usize that counts all nodes (both leaves and internal nodes). Verify that count_nodes(t) == count_leaves(t) + count_internal(t).count_internal<T>(tree: &Tree<T>) -> usize that counts only nodes that have at least one non-leaf child.leaf_fraction<T>(tree: &Tree<T>) -> f64 that returns count_leaves(t) / count_nodes(t) as f64. For a complete binary tree of depth d, this is approximately 0.5.count_nodes<T>(tree: &Tree<T>) -> usize that counts ALL nodes (leaves + internal). Verify that count_leaves + count_internal_nodes == count_nodes in tests.leaf_ratio(tree: &Tree<T>) -> f64 returning the fraction of all nodes that are leaves. For a complete binary tree, this approaches 0.5 as size grows.