034 — Construct a Complete Binary Tree
Tutorial Video
Text description (accessibility)
This video demonstrates the "034 — Construct a Complete Binary Tree" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. A complete binary tree of n nodes (OCaml 99 Problems #34) fills levels from left to right — every level except possibly the last is fully filled, and the last level has all nodes to the left. Key difference from OCaml: 1. **Array representation**: Complete binary trees map perfectly to arrays (level
Tutorial
The Problem
A complete binary tree of n nodes (OCaml 99 Problems #34) fills levels from left to right — every level except possibly the last is fully filled, and the last level has all nodes to the left. This is the structural property of binary heaps and array-based trees. Index i has children at 2i+1 and 2i+2; parent at (i-1)/2.
Complete binary trees are used in heap data structures (priority queues: BinaryHeap in Rust's standard library), binary indexed trees (Fenwick trees for prefix sums), and segment trees. The construction algorithm distributes n nodes optimally to minimize height, which is ⌊log₂(n)⌋ + 1.
🎯 Learning Outcomes
(n-1)/2 nodes (or (n)/2 depending on fullness of last level)count_nodes(complete_binary_tree(n)) == n for all n in testsCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
BinaryHeap uses Vec internally. The recursive tree is rarely used in practice for heaps.⌊log₂(n)⌋. Rust: (n as f64).log2().floor() as usize. OCaml: int_of_float (log (float_of_int n) /. log 2.0).BinaryHeap::from(vec) uses the Floyd heapify algorithm (O(n)) rather than constructing a complete tree first. Understanding the tree structure helps reason about heap operations.complete_binary_tree n generates the canonical complete binary tree with n nodes.if n <= 0 then Leaf else Node((), complete_binary_tree(n/2), complete_binary_tree(n - n/2)) splits n nodes between left and right subtrees. The left subtree gets the larger share for left-filling.() as value type:** The OCaml version uses unit () as the node value — only the structure matters, not the payload. Rust uses () analogously: Tree<()> for structure-only trees.OCaml Approach
OCaml's version: let rec complete_binary_tree n = if n = 0 then Leaf else let l = (n - 1) / 2 + (if (n - 1) mod 2 > 0 then 1 else 0) in Node ('x', complete_binary_tree l, complete_binary_tree (n - 1 - l)). The formula ensures the left subtree is at least as large as the right, maintaining left-justification.
Full Source
#![allow(clippy::all)]
// Placeholder — pending conversionDeep Comparison
OCaml vs Rust: Complete 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
is_complete<T>(tree: &Tree<T>) -> bool that checks if a tree is complete. Use level-order traversal — once you see a non-full node, all subsequent nodes must be leaves.Vec<i32>. For a sorted array, the median becomes the root, left half becomes the left subtree, right half the right subtree.heap_insert and heap_extract_min that maintain the heap property. Compare with Rust's built-in BinaryHeap.is_complete<T>(tree: &Tree<T>) -> bool that checks whether a given tree is a complete binary tree (all levels full except possibly last, last filled left-to-right).nth_node<T: Clone>(tree: &Tree<T>, n: usize) -> Option<T> returning the n-th node's value.