1047: Flat Binary Tree in Vec

Difficulty: Intermediate Category: Data Structures Concept: Implicit binary tree using array indexing: children at 2i+1 and 2i+2 Key Insight: A flat tree stores a complete binary tree in a contiguous array with no pointers — children and parents are computed by arithmetic. This is how `BinaryHeap` works internally and enables cache-friendly tree operations.

// 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]);
    }
}

fn main() {
    basic_tree();
    level_order_test();
    heap_test();
    println!("✓ All tests passed");
}

#[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"

📊 Detailed 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