Trees in depth

Tree Fundamentals

A tree is a connected, acyclic graph with a distinguished root node. Every node except the root has exactly one parent, and zero or more children. A node with no children is called a leaf.

        [A]           <-- root (depth 0)
       /   \
     [B]   [C]        <-- depth 1
    / \       \
  [D] [E]    [F]      <-- depth 2 (D, E, F are leaves)

BST: Search, Insert, Delete

A Binary Search Tree enforces the invariant: for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This gives O(log n) average-case search, insert, and delete.

        [8]
       /   \
     [3]   [10]
    / \       \
  [1] [6]    [14]
      / \    /
    [4] [7] [13]

  In-order traversal: 1, 3, 4, 6, 7, 8, 10, 13, 14  (sorted!)

AVL Trees & Red-Black Trees

Self-balancing BSTs automatically maintain a bounded height after insertions and deletions, guaranteeing O(log n) worst-case operations.

AVL Trees

Strict balance: for every node, the heights of left and right subtrees differ by at most 1. Rebalancing uses rotations (single or double) after each modification. Lookups are slightly faster than Red-Black trees because the tree is more tightly balanced.

Red-Black Trees

Relaxed balance: nodes are colored red or black with rules that ensure the longest path is at most 2x the shortest. Fewer rotations on insert/delete compared to AVL, making writes faster. Used extensively in practice.

  Before:        After:
    [C]           [B]
   /             /   \
  [B]          [A]   [C]
 /
[A]

Multi-Way Trees for Disk

B-Trees generalize BSTs by allowing each node to hold multiple keys and have multiple children. They are optimized for systems that read/write large blocks of data — particularly databases and file systems.

B-Tree

A B-Tree of order m allows each node up to m - 1 keys and m children. All leaves are at the same depth, guaranteeing O(log n) operations. The wide branching factor minimizes disk I/O by reducing tree height.

B+ Tree

A variant where all actual data resides in the leaves, and internal nodes store only keys for routing. Leaf nodes are linked together in a doubly-linked list, enabling efficient range scans.

Heaps & Priority Queues

A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is smaller than its children; in a max-heap, every parent is larger. Heaps are typically stored as arrays with no pointers needed.

        [1]
       /   \
     [3]   [5]
    / \    /
  [7] [9] [8]

  Parent of i: (i-1)/2
  Left child:  2i + 1
  Right child: 2i + 2

Applications

Specialized Trees

Trie (Prefix Tree)

A trie stores strings character-by-character, with each edge representing a character. Lookup time is O(L) where L is the length of the query string — independent of how many strings are stored.

       (root)
      /      \
    c          d
    |          |
    a          o
   / \         |
  t*  r*       g*
      |
      d*

  * = end of word

Segment Tree

A segment tree builds on an array to answer range queries (sum, min, max, GCD) and perform point/range updates in O(log n). Each node stores the aggregate for a range of the original array.

Fenwick Tree (Binary Indexed Tree)

A more space-efficient alternative to segment trees for prefix sums and point updates. Uses clever bit manipulation — O(log n) for both query and update, but limited to operations with an inverse (like addition).

When to Use What