034 Intermediate GitHub

034 — Construct a Complete Binary Tree

Functional Programming

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

• Construct a complete binary tree from n node values

• Understand the relationship between node count, tree height, and completeness

• Use the recursive formula: left subtree gets (n-1)/2 nodes (or (n)/2 depending on fullness of last level)

• Verify completeness: all levels full except possibly the last, which is left-justified

• Connect complete binary trees to heap data structures

• Build a complete binary tree using the formula: left subtree gets ceiling(n/2) nodes, right gets floor(n/2)

• Verify count_nodes(complete_binary_tree(n)) == n for all n in tests

Code Example

#![allow(clippy::all)]
// Construct a complete binary tree of n nodes, left-justified (OCaml 99 Problems #34).
#[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 count_nodes<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + count_nodes(l) + count_nodes(r),
    }
}

pub fn complete_binary_tree(n: usize) -> Tree<()> {
    if n == 0 {
        return Tree::Leaf;
    }
    let remaining = n - 1;
    let left_count = remaining / 2 + remaining % 2;
    let right_count = remaining - left_count;
    Tree::node((), complete_binary_tree(left_count), complete_binary_tree(right_count))
}

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

    #[test]
    fn test_node_count_matches_n() {
        for n in 0..20 {
            assert_eq!(count_nodes(&complete_binary_tree(n)), n);
        }
    }

    #[test]
    fn test_zero_nodes_is_leaf() {
        assert_eq!(complete_binary_tree(0), Tree::Leaf);
    }

    #[test]
    fn test_left_is_at_least_as_large_as_right() {
        fn min_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + min_depth(l).min(min_depth(r)),
            }
        }
        fn max_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + max_depth(l).max(max_depth(r)),
            }
        }
        // A complete tree's min and max leaf depth differ by at most 1.
        let t = complete_binary_tree(10);
        assert!(max_depth(&t) - min_depth(&t) <= 1);
    }
}

(* Complete Tree *)
(* OCaml 99 Problems #34 *)

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

let rec count_nodes = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + count_nodes l + count_nodes r

let rec complete_binary_tree n =
  if n = 0 then Leaf
  else
    let remaining = n - 1 in
    let l = remaining / 2 + (remaining mod 2) in
    Node ('x', complete_binary_tree l, complete_binary_tree (remaining - l))

(* Tests *)
let () =
  for n = 0 to 19 do
    assert (count_nodes (complete_binary_tree n) = n)
  done;
  assert (complete_binary_tree 0 = Leaf);
  print_endline "✓ OCaml tests passed"

Key Differences

Array representation: Complete binary trees map perfectly to arrays (level-order indexing). Rust's BinaryHeap uses Vec internally. The recursive tree is rarely used in practice for heaps.

Height calculation: For n nodes, height is ⌊log₂(n)⌋. Rust: (n as f64).log2().floor() as usize. OCaml: int_of_float (log (float_of_int n) /. log 2.0).

Left vs right subtree size: The exact formula for how many nodes go to each subtree depends on which level is partial. Off-by-one errors here produce trees that are complete but not left-justified.

Heapify: Rust's standard 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 vs perfect: A complete binary tree has all levels fully filled except possibly the last, which is filled left-to-right. A perfect tree has all leaves at the same depth. The complete_binary_tree n generates the canonical complete binary tree with n nodes.

Recursive construction: 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.

Left-heavy filling: When n is odd, the left subtree gets one more node than the right. This ensures the last level fills left-to-right, which is the defining property of a complete binary tree.

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)]
// Construct a complete binary tree of n nodes, left-justified (OCaml 99 Problems #34).
#[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 count_nodes<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node(_, l, r) => 1 + count_nodes(l) + count_nodes(r),
    }
}

pub fn complete_binary_tree(n: usize) -> Tree<()> {
    if n == 0 {
        return Tree::Leaf;
    }
    let remaining = n - 1;
    let left_count = remaining / 2 + remaining % 2;
    let right_count = remaining - left_count;
    Tree::node((), complete_binary_tree(left_count), complete_binary_tree(right_count))
}

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

    #[test]
    fn test_node_count_matches_n() {
        for n in 0..20 {
            assert_eq!(count_nodes(&complete_binary_tree(n)), n);
        }
    }

    #[test]
    fn test_zero_nodes_is_leaf() {
        assert_eq!(complete_binary_tree(0), Tree::Leaf);
    }

    #[test]
    fn test_left_is_at_least_as_large_as_right() {
        fn min_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + min_depth(l).min(min_depth(r)),
            }
        }
        fn max_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + max_depth(l).max(max_depth(r)),
            }
        }
        // A complete tree's min and max leaf depth differ by at most 1.
        let t = complete_binary_tree(10);
        assert!(max_depth(&t) - min_depth(&t) <= 1);
    }
}

(* Complete Tree *)
(* OCaml 99 Problems #34 *)

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

let rec count_nodes = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + count_nodes l + count_nodes r

let rec complete_binary_tree n =
  if n = 0 then Leaf
  else
    let remaining = n - 1 in
    let l = remaining / 2 + (remaining mod 2) in
    Node ('x', complete_binary_tree l, complete_binary_tree (remaining - l))

(* Tests *)
let () =
  for n = 0 to 19 do
    assert (count_nodes (complete_binary_tree n) = n)
  done;
  assert (complete_binary_tree 0 = Leaf);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_node_count_matches_n() {
        for n in 0..20 {
            assert_eq!(count_nodes(&complete_binary_tree(n)), n);
        }
    }

    #[test]
    fn test_zero_nodes_is_leaf() {
        assert_eq!(complete_binary_tree(0), Tree::Leaf);
    }

    #[test]
    fn test_left_is_at_least_as_large_as_right() {
        fn min_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + min_depth(l).min(min_depth(r)),
            }
        }
        fn max_depth<T>(tree: &Tree<T>) -> usize {
            match tree {
                Tree::Leaf => 0,
                Tree::Node(_, l, r) => 1 + max_depth(l).max(max_depth(r)),
            }
        }
        // A complete tree's min and max leaf depth differ by at most 1.
        let t = complete_binary_tree(10);
        assert!(max_depth(&t) - min_depth(&t) <= 1);
    }
}

Deep 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

Verify completeness: Write 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.

From sorted array: Build a complete binary search tree from a sorted Vec<i32>. For a sorted array, the median becomes the root, left half becomes the left subtree, right half the right subtree.

Heap operations: Using your complete tree, implement heap_insert and heap_extract_min that maintain the heap property. Compare with Rust's built-in BinaryHeap.

Validate completeness: Write 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).

N-th node: In a complete binary tree with n nodes, the nodes can be numbered 1..n in BFS order. Write nth_node<T: Clone>(tree: &Tree<T>, n: usize) -> Option<T> returning the n-th node's value.

Open Source Repos

functional-rust

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

Rust