Hierarchical Data Structures: Trees, Balanced BSTs, Heaps, and Tries

Trees are non-linear, hierarchical data structures composed of nodes connected by edges. They provide efficient logarithmic search, ordered traversals, priority queuing, and prefix matching across database indexing (B-Trees), memory management (Red-Black Trees), and scheduling algorithms (Heaps).

⚡ Quick Dive

Tree Data Structures Complexity Matrix

Structure Search Insertion Deletion Space Primary Real-World Application
Unsorted Binary Tree $O(n)$ $O(1)^*$ $O(n)$ $O(n)$ Expression evaluation, ASTs in compilers
Binary Search Tree (BST) $O(\log n)$ avg / $O(n)$ worst $O(\log n)$ avg / $O(n)$ worst $O(\log n)$ avg / $O(n)$ worst $O(n)$ Ordered data storage (unbalanced risks skew)
AVL Tree (Strictly Balanced) $O(\log n)$ $O(\log n)$ $O(\log n)$ $O(n)$ Read-heavy lookups (faster search than Red-Black)
Red-Black Tree $O(\log n)$ $O(\log n)$ $O(\log n)$ $O(n)$ Standard library maps (C++ std::map, Java TreeMap, Linux CFS)
Binary Heap (Priority Queue) $O(1)$ (Peek Min/Max) $O(\log n)$ (Push) $O(\log n)$ (Pop Min/Max) $O(n)$ Dijkstra's shortest path, CPU task scheduling
Trie (Prefix Tree) $O(L)$ ($L$ = string length) $O(L)$ $O(L)$ $O(N \cdot L \cdot \Sigma

📖 Extended Guide

1. Tree Terminology & Topologies

        ( Root: 10 )              ◄── Level 0 (Height 2)
       /            \
  ( Node: 5 )    ( Node: 15 )     ◄── Level 1 (Height 1)
   /      \       /        \
(Leaf:2)(Leaf:7)(Leaf:12)(Leaf:18) ◄── Level 2 (Height 0, Leaves)
  • Height of Node: Number of edges on the longest path from node to a leaf.
  • Depth of Node: Number of edges from the root to the node.
  • Full Binary Tree: Every node has 0 or 2 children.
  • Complete Binary Tree: Every level is completely filled except possibly the last, which is filled from left to right.
  • Perfect Binary Tree: All interior nodes have 2 children and all leaves are at the same level (Total nodes $= 2^{h+1} - 1$).

2. Tree Traversals

Depth-First Traversals (DFS):

  1. In-Order (Left $\to$ Root $\to$ Right): Yields sorted order in a BST.
  2. Pre-Order (Root $\to$ Left $\to$ Right): Used for serializing/copying trees.
  3. Post-Order (Left $\to$ Right $\to$ Root): Used for bottom-up cleanup (deleting trees, calculating directory sizes).

Breadth-First Traversal (BFS / Level-Order):

  • Uses an explicit queue to traverse level-by-level.

3. Binary Search Tree (BST) Operations

BST Property:

For every node $X$, all keys in the left subtree are $< X$, and all keys in the right subtree are $> X$.

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// Insert adds a value to the BST in O(log n) average time.
func Insert(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}
	if val < root.Val {
		root.Left = Insert(root.Left, val)
	} else if val > root.Val {
		root.Right = Insert(root.Right, val)
	}
	return root
}

4. Self-Balancing Trees: AVL vs. Red-Black

Unbalanced BSTs can degenerate into $O(n)$ linked lists on sorted inputs.

Degenerate Skewed BST (O(n)):        Balanced AVL / Red-Black Tree (O(log n)):
( 1 )                                             ( 2 )
   \                                             /     \
   ( 2 )                                       ( 1 )   ( 3 )
      \
      ( 3 )
  • AVL Trees: Enforce balance factor $|Height(Left) - Height(Right)| \le 1$. Strict balance gives faster searches but requires more rotations on insertion/deletion.
  • Red-Black Trees: Enforce color invariants (root is black, no consecutive red nodes, equal black depth to all leaves). Looser balance guarantees maximum height $\le 2\log_2(n+1)$, resulting in faster inserts and deletes.

5. Binary Heaps & Priority Queues

A Binary Heap is a complete binary tree stored compactly in a flat array (zero pointer overhead):

Array Representation: [ 2, 5, 8, 12, 16, 23, 38 ]
Index Formulas:
- Left Child of index i  = 2*i + 1
- Right Child of index i = 2*i + 2
- Parent of index i       = (i - 1) / 2

Min-Heap Implementation in Go:

package main

import "fmt"

type MinHeap struct {
	data []int
}

func (h *MinHeap) Push(val int) {
	h.data = append(h.data, val)
	h.siftUp(len(h.data) - 1)
}

func (h *MinHeap) Pop() (int, bool) {
	if len(h.data) == 0 {
		return 0, false
	}
	minVal := h.data[0]
	lastIdx := len(h.data) - 1
	h.data[0] = h.data[lastIdx]
	h.data = h.data[:lastIdx]
	if len(h.data) > 0 {
		h.siftDown(0)
	}
	return minVal, true
}

func (h *MinHeap) siftUp(idx int) {
	for idx > 0 {
		parent := (idx - 1) / 2
		if h.data[idx] >= h.data[parent] {
			break
		}
		h.data[idx], h.data[parent] = h.data[parent], h.data[idx]
		idx = parent
	}
}

func (h *MinHeap) siftDown(idx int) {
	n := len(h.data)
	for {
		smallest := idx
		left := 2*idx + 1
		right := 2*idx + 2

		if left < n && h.data[left] < h.data[smallest] {
			smallest = left
		}
		if right < n && h.data[right] < h.data[smallest] {
			smallest = right
		}
		if smallest == idx {
			break
		}
		h.data[idx], h.data[smallest] = h.data[smallest], h.data[idx]
		idx = smallest
	}
}

func main() {
	h := &MinHeap{}
	for _, v := range []int{15, 10, 20, 8, 12} {
		h.Push(v)
	}
	for len(h.data) > 0 {
		val, _ := h.Pop()
		fmt.Printf("%d ", val) // 8 10 12 15 20 (Sorted Output)
	}
	fmt.Println()
}

6. Prefix Trees (Trie)

A Trie is a specialized search tree used to store associative keys (typically strings).

Trie for keys: "app", "apple", "apt"
        (root)
          │
         [a]
          │
         [p]
         / \
    (end)[p] [t](end)
       │
      [l]
       │
      [e](end)
  • Query time is strictly $O(L)$ where $L$ is the length of the query string, completely independent of the total number of words in the dictionary $N$.
⌂ All Guides