1047 Intermediate

1047-flat-tree — Flat Binary Tree in Vec

Functional Programming

Tutorial

The Problem

Binary heaps and segment trees store binary trees in arrays using the heap indexing formula: for a node at index i, the left child is at 2*i+1, the right child at 2*i+2, and the parent at (i-1)/2. This array-based tree representation eliminates pointer overhead, maximizes cache locality, and enables O(1) parent/child navigation without storing explicit pointers.

This pattern is the implementation technique behind binary heaps (BinaryHeap), segment trees for range queries, and complete binary trees in competitive programming.

🎯 Learning Outcomes

• Represent a binary tree as a flat Vec<T> using heap indexing

• Navigate parent, left child, and right child using the index formulas

• Identify leaf nodes by checking whether the child index is in bounds

• Perform in-order, pre-order, and level-order traversals

• Understand the cache locality advantages over pointer-based trees

Code Example

#![allow(clippy::all)]
// 1047: Flat Binary Tree in Vec
// Children of node i: left = 2*i+1, right = 2*i+2, parent = (i-1)/2

struct FlatTree<T> {
    data: Vec<T>,
}

impl<T: std::fmt::Debug + Clone + Ord> FlatTree<T> {
    fn new(data: Vec<T>) -> Self {
        FlatTree { data }
    }

    fn left_child(i: usize) -> usize {
        2 * i + 1
    }
    fn right_child(i: usize) -> usize {
        2 * i + 2
    }
    fn parent(i: usize) -> usize {
        (i - 1) / 2
    }

    fn get(&self, i: usize) -> Option<&T> {
        self.data.get(i)
    }

    fn is_leaf(&self, i: usize) -> bool {
        Self::left_child(i) >= self.data.len()
    }

    fn left(&self, i: usize) -> Option<&T> {
        self.data.get(Self::left_child(i))
    }

    fn right(&self, i: usize) -> Option<&T> {
        self.data.get(Self::right_child(i))
    }

    /// Level-order traversal (returns levels)
    fn levels(&self) -> Vec<Vec<&T>> {
        let mut result = Vec::new();
        let mut start = 0;
        let mut level_size = 1;

        while start < self.data.len() {
            let end = (start + level_size).min(self.data.len());
            result.push(self.data[start..end].iter().collect());
            start = end;
            level_size *= 2;
        }
        result
    }

    /// Heapify: build max-heap in place
    fn heapify(&mut self) {
        let n = self.data.len();
        for i in (0..n / 2).rev() {
            self.sift_down(i);
        }
    }

    fn sift_down(&mut self, mut i: usize) {
        let n = self.data.len();
        loop {
            let mut largest = i;
            let l = Self::left_child(i);
            let r = Self::right_child(i);

            if l < n && self.data[l] > self.data[largest] {
                largest = l;
            }
            if r < n && self.data[r] > self.data[largest] {
                largest = r;
            }

            if largest == i {
                break;
            }
            self.data.swap(i, largest);
            i = largest;
        }
    }

    /// Depth of the tree
    fn depth(&self) -> usize {
        if self.data.is_empty() {
            0
        } else {
            (self.data.len() as f64).log2().floor() as usize + 1
        }
    }
}

fn basic_tree() {
    //       1
    //      / \
    //     2   3
    //    / \ /
    //   4  5 6
    let tree = FlatTree::new(vec![1, 2, 3, 4, 5, 6]);

    assert_eq!(tree.get(0), Some(&1)); // Root
    assert_eq!(tree.left(0), Some(&2));
    assert_eq!(tree.right(0), Some(&3));
    assert_eq!(tree.left(1), Some(&4));
    assert_eq!(tree.right(1), Some(&5));
    assert_eq!(tree.left(2), Some(&6));
    assert_eq!(tree.right(2), None); // No right child for node 2

    assert!(tree.is_leaf(3));
    assert!(!tree.is_leaf(0));
}

fn level_order_test() {
    let tree = FlatTree::new(vec![1, 2, 3, 4, 5, 6, 7]);
    let levels = tree.levels();
    assert_eq!(levels.len(), 3);
    assert_eq!(levels[0], vec![&1]);
    assert_eq!(levels[1], vec![&2, &3]);
    assert_eq!(levels[2], vec![&4, &5, &6, &7]);
}

fn heap_test() {
    let mut tree = FlatTree::new(vec![3, 1, 4, 1, 5, 9, 2, 6]);
    tree.heapify();

    // Root should be max
    assert_eq!(tree.get(0), Some(&9));

    // Heap property: parent >= children
    for i in 1..tree.data.len() {
        let p = FlatTree::<i32>::parent(i);
        assert!(
            tree.data[p] >= tree.data[i],
            "Heap violation: parent[{}]={:?} < child[{}]={:?}",
            p,
            tree.data[p],
            i,
            tree.data[i]
        );
    }
}

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

    #[test]
    fn test_basic() {
        basic_tree();
    }

    #[test]
    fn test_levels() {
        level_order_test();
    }

    #[test]
    fn test_heap() {
        heap_test();
    }

    #[test]
    fn test_depth() {
        assert_eq!(FlatTree::new(vec![1]).depth(), 1);
        assert_eq!(FlatTree::new(vec![1, 2, 3]).depth(), 2);
        assert_eq!(FlatTree::new(vec![1, 2, 3, 4, 5, 6, 7]).depth(), 3);
    }

    #[test]
    fn test_empty() {
        let tree: FlatTree<i32> = FlatTree::new(vec![]);
        assert_eq!(tree.depth(), 0);
        assert_eq!(tree.get(0), None);
    }
}

(* 1047: Flat Binary Tree in Array *)
(* Children of node i: left = 2i+1, right = 2i+2, parent = (i-1)/2 *)

(* Approach 1: Basic flat tree operations *)
let left_child i = 2 * i + 1
let right_child i = 2 * i + 2
let parent i = (i - 1) / 2

let basic_tree () =
  (*       1
         /   \
        2     3
       / \   /
      4   5 6      *)
  let tree = [|1; 2; 3; 4; 5; 6|] in
  let n = Array.length tree in
  (* Root *)
  assert (tree.(0) = 1);
  (* Children of root *)
  assert (tree.(left_child 0) = 2);
  assert (tree.(right_child 0) = 3);
  (* Children of node 1 (value=2) *)
  assert (tree.(left_child 1) = 4);
  assert (tree.(right_child 1) = 5);
  (* Parent of node 5 (index=4) *)
  assert (tree.(parent 4) = 2);
  (* Leaf check *)
  let is_leaf i = left_child i >= n in
  assert (is_leaf 3);
  assert (not (is_leaf 0))

(* Approach 2: Level-order traversal *)
let level_order tree =
  let n = Array.length tree in
  let levels = ref [] in
  let i = ref 0 in
  let level_size = ref 1 in
  while !i < n do
    let level = ref [] in
    for j = 0 to min (!level_size - 1) (n - !i - 1) do
      level := tree.(!i + j) :: !level
    done;
    levels := List.rev !level :: !levels;
    i := !i + !level_size;
    level_size := !level_size * 2
  done;
  List.rev !levels

let level_order_test () =
  let tree = [|1; 2; 3; 4; 5; 6; 7|] in
  let levels = level_order tree in
  assert (levels = [[1]; [2; 3]; [4; 5; 6; 7]])

(* Approach 3: Build max-heap (heapify) *)
let swap arr i j =
  let tmp = arr.(i) in
  arr.(i) <- arr.(j);
  arr.(j) <- tmp

let rec sift_down arr n i =
  let largest = ref i in
  let l = left_child i in
  let r = right_child i in
  if l < n && arr.(l) > arr.(!largest) then largest := l;
  if r < n && arr.(r) > arr.(!largest) then largest := r;
  if !largest <> i then begin
    swap arr i !largest;
    sift_down arr n !largest
  end

let heapify arr =
  let n = Array.length arr in
  for i = n / 2 - 1 downto 0 do
    sift_down arr n i
  done

let heap_test () =
  let arr = [|3; 1; 4; 1; 5; 9; 2; 6|] in
  heapify arr;
  (* After heapify, root should be max *)
  assert (arr.(0) = 9);
  (* Heap property: parent >= children *)
  let n = Array.length arr in
  for i = 1 to n - 1 do
    assert (arr.(parent i) >= arr.(i))
  done

let () =
  basic_tree ();
  level_order_test ();
  heap_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Identical formulas: Both languages use the same 2*i+1, 2*i+2, (i-1)/2 index arithmetic — this is mathematical, not language-specific.

Bounds checking: Rust's Vec::get(i) returns Option<&T> for safe out-of-bounds access; OCaml requires manual bounds checking or raises Invalid_argument.

Heap sort: Rust's BinaryHeap::sort uses this exact representation internally; OCaml's Array.sort uses a different algorithm.

Generic constraints: Rust's FlatTree<T: Ord> uses trait bounds for comparison; OCaml uses polymorphic comparison or a functor.

OCaml Approach

OCaml's flat tree uses an array with the same index arithmetic:

let left_child i = 2 * i + 1
let right_child i = 2 * i + 2
let parent i = (i - 1) / 2

let is_leaf arr i = left_child i >= Array.length arr

let get arr i =
  if i < Array.length arr then Some arr.(i) else None

The formulas are identical. OCaml arrays are mutable by default, enabling in-place heap sort.

Full Source

#![allow(clippy::all)]
// 1047: Flat Binary Tree in Vec
// Children of node i: left = 2*i+1, right = 2*i+2, parent = (i-1)/2

struct FlatTree<T> {
    data: Vec<T>,
}

impl<T: std::fmt::Debug + Clone + Ord> FlatTree<T> {
    fn new(data: Vec<T>) -> Self {
        FlatTree { data }
    }

    fn left_child(i: usize) -> usize {
        2 * i + 1
    }
    fn right_child(i: usize) -> usize {
        2 * i + 2
    }
    fn parent(i: usize) -> usize {
        (i - 1) / 2
    }

    fn get(&self, i: usize) -> Option<&T> {
        self.data.get(i)
    }

    fn is_leaf(&self, i: usize) -> bool {
        Self::left_child(i) >= self.data.len()
    }

    fn left(&self, i: usize) -> Option<&T> {
        self.data.get(Self::left_child(i))
    }

    fn right(&self, i: usize) -> Option<&T> {
        self.data.get(Self::right_child(i))
    }

    /// Level-order traversal (returns levels)
    fn levels(&self) -> Vec<Vec<&T>> {
        let mut result = Vec::new();
        let mut start = 0;
        let mut level_size = 1;

        while start < self.data.len() {
            let end = (start + level_size).min(self.data.len());
            result.push(self.data[start..end].iter().collect());
            start = end;
            level_size *= 2;
        }
        result
    }

    /// Heapify: build max-heap in place
    fn heapify(&mut self) {
        let n = self.data.len();
        for i in (0..n / 2).rev() {
            self.sift_down(i);
        }
    }

    fn sift_down(&mut self, mut i: usize) {
        let n = self.data.len();
        loop {
            let mut largest = i;
            let l = Self::left_child(i);
            let r = Self::right_child(i);

            if l < n && self.data[l] > self.data[largest] {
                largest = l;
            }
            if r < n && self.data[r] > self.data[largest] {
                largest = r;
            }

            if largest == i {
                break;
            }
            self.data.swap(i, largest);
            i = largest;
        }
    }

    /// Depth of the tree
    fn depth(&self) -> usize {
        if self.data.is_empty() {
            0
        } else {
            (self.data.len() as f64).log2().floor() as usize + 1
        }
    }
}

fn basic_tree() {
    //       1
    //      / \
    //     2   3
    //    / \ /
    //   4  5 6
    let tree = FlatTree::new(vec![1, 2, 3, 4, 5, 6]);

    assert_eq!(tree.get(0), Some(&1)); // Root
    assert_eq!(tree.left(0), Some(&2));
    assert_eq!(tree.right(0), Some(&3));
    assert_eq!(tree.left(1), Some(&4));
    assert_eq!(tree.right(1), Some(&5));
    assert_eq!(tree.left(2), Some(&6));
    assert_eq!(tree.right(2), None); // No right child for node 2

    assert!(tree.is_leaf(3));
    assert!(!tree.is_leaf(0));
}

fn level_order_test() {
    let tree = FlatTree::new(vec![1, 2, 3, 4, 5, 6, 7]);
    let levels = tree.levels();
    assert_eq!(levels.len(), 3);
    assert_eq!(levels[0], vec![&1]);
    assert_eq!(levels[1], vec![&2, &3]);
    assert_eq!(levels[2], vec![&4, &5, &6, &7]);
}

fn heap_test() {
    let mut tree = FlatTree::new(vec![3, 1, 4, 1, 5, 9, 2, 6]);
    tree.heapify();

    // Root should be max
    assert_eq!(tree.get(0), Some(&9));

    // Heap property: parent >= children
    for i in 1..tree.data.len() {
        let p = FlatTree::<i32>::parent(i);
        assert!(
            tree.data[p] >= tree.data[i],
            "Heap violation: parent[{}]={:?} < child[{}]={:?}",
            p,
            tree.data[p],
            i,
            tree.data[i]
        );
    }
}

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

    #[test]
    fn test_basic() {
        basic_tree();
    }

    #[test]
    fn test_levels() {
        level_order_test();
    }

    #[test]
    fn test_heap() {
        heap_test();
    }

    #[test]
    fn test_depth() {
        assert_eq!(FlatTree::new(vec![1]).depth(), 1);
        assert_eq!(FlatTree::new(vec![1, 2, 3]).depth(), 2);
        assert_eq!(FlatTree::new(vec![1, 2, 3, 4, 5, 6, 7]).depth(), 3);
    }

    #[test]
    fn test_empty() {
        let tree: FlatTree<i32> = FlatTree::new(vec![]);
        assert_eq!(tree.depth(), 0);
        assert_eq!(tree.get(0), None);
    }
}

(* 1047: Flat Binary Tree in Array *)
(* Children of node i: left = 2i+1, right = 2i+2, parent = (i-1)/2 *)

(* Approach 1: Basic flat tree operations *)
let left_child i = 2 * i + 1
let right_child i = 2 * i + 2
let parent i = (i - 1) / 2

let basic_tree () =
  (*       1
         /   \
        2     3
       / \   /
      4   5 6      *)
  let tree = [|1; 2; 3; 4; 5; 6|] in
  let n = Array.length tree in
  (* Root *)
  assert (tree.(0) = 1);
  (* Children of root *)
  assert (tree.(left_child 0) = 2);
  assert (tree.(right_child 0) = 3);
  (* Children of node 1 (value=2) *)
  assert (tree.(left_child 1) = 4);
  assert (tree.(right_child 1) = 5);
  (* Parent of node 5 (index=4) *)
  assert (tree.(parent 4) = 2);
  (* Leaf check *)
  let is_leaf i = left_child i >= n in
  assert (is_leaf 3);
  assert (not (is_leaf 0))

(* Approach 2: Level-order traversal *)
let level_order tree =
  let n = Array.length tree in
  let levels = ref [] in
  let i = ref 0 in
  let level_size = ref 1 in
  while !i < n do
    let level = ref [] in
    for j = 0 to min (!level_size - 1) (n - !i - 1) do
      level := tree.(!i + j) :: !level
    done;
    levels := List.rev !level :: !levels;
    i := !i + !level_size;
    level_size := !level_size * 2
  done;
  List.rev !levels

let level_order_test () =
  let tree = [|1; 2; 3; 4; 5; 6; 7|] in
  let levels = level_order tree in
  assert (levels = [[1]; [2; 3]; [4; 5; 6; 7]])

(* Approach 3: Build max-heap (heapify) *)
let swap arr i j =
  let tmp = arr.(i) in
  arr.(i) <- arr.(j);
  arr.(j) <- tmp

let rec sift_down arr n i =
  let largest = ref i in
  let l = left_child i in
  let r = right_child i in
  if l < n && arr.(l) > arr.(!largest) then largest := l;
  if r < n && arr.(r) > arr.(!largest) then largest := r;
  if !largest <> i then begin
    swap arr i !largest;
    sift_down arr n !largest
  end

let heapify arr =
  let n = Array.length arr in
  for i = n / 2 - 1 downto 0 do
    sift_down arr n i
  done

let heap_test () =
  let arr = [|3; 1; 4; 1; 5; 9; 2; 6|] in
  heapify arr;
  (* After heapify, root should be max *)
  assert (arr.(0) = 9);
  (* Heap property: parent >= children *)
  let n = Array.length arr in
  for i = 1 to n - 1 do
    assert (arr.(parent i) >= arr.(i))
  done

let () =
  basic_tree ();
  level_order_test ();
  heap_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        basic_tree();
    }

    #[test]
    fn test_levels() {
        level_order_test();
    }

    #[test]
    fn test_heap() {
        heap_test();
    }

    #[test]
    fn test_depth() {
        assert_eq!(FlatTree::new(vec![1]).depth(), 1);
        assert_eq!(FlatTree::new(vec![1, 2, 3]).depth(), 2);
        assert_eq!(FlatTree::new(vec![1, 2, 3, 4, 5, 6, 7]).depth(), 3);
    }

    #[test]
    fn test_empty() {
        let tree: FlatTree<i32> = FlatTree::new(vec![]);
        assert_eq!(tree.depth(), 0);
        assert_eq!(tree.get(0), None);
    }
}

Deep Comparison

Flat Binary Tree in Vec — Comparison

Core Insight

A flat tree represents a complete binary tree in an array: node i has children at 2i+1 and 2i+2, parent at (i-1)/2. No pointers, no allocations — just arithmetic. Both languages use this identically; the difference is just array vs Vec syntax.

OCaml Approach

• Array-based: tree.(i), tree.(2*i+1), etc.

• Mutable array for heapify

• swap and sift_down with imperative loops

• Level-order: iterate with doubling level sizes

Rust Approach

• Vec<T> with index arithmetic

• data.swap(i, j) built-in

• sift_down with loop (no recursion needed)

• data.get(i) returns Option for safe access

• Same indexing formulas as any language

Comparison Table

Feature	OCaml	Rust
Storage	`'a array`	`Vec<T>`
Access	`arr.(i)`	`vec[i]` / `vec.get(i)`
Swap	Manual temp var	`vec.swap(i, j)`
Bounds check	Runtime exception	Panic or `get()` → Option
Heapify	Imperative loop	Imperative loop
Cache locality	Good (array)	Good (Vec)
Use case	Same: heaps, segment trees	Same: heaps, segment trees

Exercises

Implement heapify(&mut self) that turns any FlatTree into a max-heap in O(n) time using the sift-down procedure.

Write in_order_traversal(&self) -> Vec<&T> that returns elements in sorted order from a heap-organized tree.

Build a SegmentTree on top of FlatTree<i64> that supports range-sum queries and point updates in O(log n).

Open Source Repos

functional-rust

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

Rust