درخت‌ها، BST، درخت‌های متوازن، Trie و HeapTrees, BSTs, Balanced Trees, Tries & Heaps

Let's build one of the most-tested families of data structures from the ground up. Trees are everywhere: in Java's TreeMap, in the index of every database you've ever queried, in your phone's autocomplete, and in the priority queue of your OS scheduler. Master this chapter and you've pocketed a huge slice of any senior-level algorithm interview.

Part 0 — words you must know

Before anything else, let's anchor a handful of words that recur throughout, each with a simple picture so you never get stuck.

With that picture, the words become easy:

• Node: any "box" in the chart; one unit of data.
• Root: the CEO — the top node, which has no parent.
• Parent / child: the direct boss-employee relationship.
• Leaf: an employee with no reports — a node with no children.
• Subtree: a manager together with everyone under them; itself a smaller tree.
• Height: the longest chain of command from CEO down to the lowest employee (counting edges).
• Size: the total number of nodes, which we call n.
• Invariant: a rule that must always hold no matter what operation you run — like "every employee has exactly one boss," which must never be violated.

Mental model: from tree to BST

Binary tree

Now let's constrain the tree: say each node has at most two children, a left (left) and a right (right). That's a binary tree. Note there's no ordering between values by default — only the at-most-two-children shape matters.

Binary search tree (BST)

A binary search tree (BST) is a binary tree that adds this ordering invariant: for every node, all keys in the left subtree are strictly smaller and all keys in the right subtree are strictly greater (assuming no duplicates). That single rule turns an ordinary binary tree into a searchable structure — because at every node you know which way to go.

Tree-shape vocabulary

A few adjectives you'll keep hearing; let's nail them in one line each:

• Complete: every level is full except possibly the last, which fills left-to-right. Heaps are exactly this shape, which is why they fit in an array.
• Full / proper: every node has either zero or exactly two children — no lonely single-child nodes.
• Perfect: all leaves sit at the same depth; a full triangle.
• Balanced: height stays around O(log n). This is what we want.

Let's look at a sample tree and its traversals. Keep this picture; we'll refer back to it:

        8                 Traversal orders on this tree:
       / \                pre  : 8 3 1 6 4 7 10 14 13   (node, left, right)
      3   10              in   : 1 3 4 6 7 8 10 13 14   (left, node, right)  -> sorted for a BST!
     / \    \             post : 1 4 7 6 3 13 14 10 8   (left, right, node)
    1   6    14           level: 8 3 10 1 6 14 4 7 13   (BFS)
       / \   /
      4   7 13

Traversals: four ways to walk a tree

A "traversal" means visiting every node in some defined order. We have three depth-first traversals (in/pre/post-order) and one breadth-first (BFS).

Node definition

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Recursive traversals

The recursive version is beautiful: you just move one line to go from in-order to pre- or post-order.

void inorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    inorder(n.left, out);
    out.add(n.val);          // move this line up for pre-order, down for post-order
    inorder(n.right, out);
}

Iterative in-order (explicit stack)

The trick: dive as far down the left spine as you can, pushing everything; then pop one at a time and visit each node's right.

List<Integer> inorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {        // dive down the left spine
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();           // leftmost unvisited node
        out.add(cur.val);
        cur = cur.right;             // then explore its right subtree
    }
    return out;
}

Iterative pre-order

List<Integer> preorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        out.add(n.val);
        if (n.right != null) stack.push(n.right); // push right FIRST so left pops first
        if (n.left != null)  stack.push(n.left);
    }
    return out;
}

Iterative post-order is the trickiest: either use two stacks, or do a modified pre-order (node, right, left) and reverse the result at the end, or track a lastVisited pointer. The reverse trick is the cleanest:

List<Integer> postorderIter(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        out.addFirst(n.val);                      // prepend -> reverses pre-order-ish output
        if (n.left != null)  stack.push(n.left);
        if (n.right != null) stack.push(n.right);
    }
    return out;
}

Level-order (BFS) with per-level grouping

Breadth-first means reading the tree floor by floor, like reading a building from the ground up. The tool here is a queue, not a stack.

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();                      // snapshot: exactly one level
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null)  q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        res.add(level);
    }
    return res;
}

Morris traversal — in-order in O(1) space

BST operations: search, insert, and the gotcha delete

Search, insert, and delete are all O(height). Search and insert are straightforward — at each node you decide left or right. But delete is where most people trip.

class BST {
    TreeNode root;

    boolean contains(int key) {
        TreeNode n = root;
        while (n != null) {
            if (key == n.val) return true;
            n = key < n.val ? n.left : n.right;
        }
        return false;
    }

    TreeNode insert(TreeNode n, int key) {
        if (n == null) return new TreeNode(key);
        if (key < n.val)      n.left  = insert(n.left, key);
        else if (key > n.val) n.right = insert(n.right, key);
        // equal -> ignore (or store a count for a multiset)
        return n;
    }

    TreeNode delete(TreeNode n, int key) {
        if (n == null) return null;
        if (key < n.val)      n.left  = delete(n.left, key);
        else if (key > n.val) n.right = delete(n.right, key);
        else {
            // found the node to delete
            if (n.left == null)  return n.right;   // 0 or 1 child (right)
            if (n.right == null) return n.left;    // 1 child (left)
            // two children: replace with in-order successor (smallest in right subtree)
            TreeNode succ = n.right;
            while (succ.left != null) succ = succ.left;
            n.val = succ.val;                       // copy successor's key up
            n.right = delete(n.right, succ.val);    // delete successor (has no left child)
        }
        return n;
    }
}

Balancing: AVL vs Red-Black

Both of these are self-balancing: after every insert/delete they rearrange themselves via rotations to keep height O(log n). But they follow different philosophies.

AVL trees maintain a strict invariant: for every node, the heights of its two subtrees differ by at most 1 (balance factor ∈ {-1, 0, +1}). Being "more rigidly balanced" means faster lookups, but inserts/deletes may need more rotations to restore that tight invariant.

Red-Black trees are looser. They color nodes red or black and enforce five rules; the key consequence is that no root-to-leaf path is more than twice as long as the shortest, so height stays ≤ 2·log₂(n+1). Fewer rotations on mutation (at most 2 for insert, 3 for delete), at the cost of a slightly taller tree.

Rotations — the primitive both share

A rotation is a local rearrangement that preserves the BST ordering but changes the shape to reduce height. Look at the diagram inside the code: y moves down and x moves up, yet A < x < B < y < C still holds.

// Right rotation around y; x becomes the new subtree root.
//        y            x
//       / \          / \
//      x   C   ->    A   y
//     / \               / \
//    A   B             B   C
TreeNode rotateRight(TreeNode y) {
    TreeNode x = y.left;
    TreeNode B = x.right;
    x.right = y;
    y.left  = B;
    // (in AVL: recompute heights of y then x here)
    return x;                 // new root of this subtree
}

Why TreeMap uses Red-Black

java.util.TreeMap and TreeSet are Red-Black trees under the hood. What's the design reasoning? A general-purpose ordered map faces a mix of reads and writes. Red-Black's cheaper rebalancing (fewer rotations per mutation) wins on that realistic mixed workload. AVL's tighter balance only pays off when reads massively dominate. On top of that, Red-Black has a bounded worst-case rotation count, which matters for predictable latency.

All of get/put/remove/ceilingKey/floorKey/firstKey are O(log n); in-order iteration is O(n) and yields sorted keys.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a"); map.put(5, "b"); map.put(20, "c");
map.firstKey();          // 5   (leftmost)
map.ceilingKey(6);       // 10  (least key >= 6)
map.floorKey(15);        // 10  (greatest key <= 15)
map.headMap(10);         // {5=b}  view of keys < 10, backed by the tree
map.subMap(5, true, 20, false); // range view, O(log n) to locate endpoints

Why databases use B-trees / B+ trees, not BSTs

A balanced BST has fan-out 2 — each node has only two children. For a billion rows its height is ~30. On disk/SSD, every node access is potentially a page read, so 30 random I/Os per lookup is catastrophic.

B-trees and B+ trees are m-way balanced trees: each node holds hundreds of keys, sized to one disk page (say 8-16 KB). With fan-out ~500, a billion rows fit in a tree of height 3-4 → just 3-4 page reads. The whole point is this: minimize I/O by maximizing fan-out.

Heaps and PriorityQueue

The heap property

A binary heap is a complete binary tree satisfying the heap property: in a min-heap every parent ≤ its children (root is the minimum); in a max-heap every parent ≥ its children (root is the maximum). Because this invariant is weaker than a BST's, a heap gives you O(1) peek at the min/max and O(log n) insert/extract, but arbitrary-value search is O(n).

Stored in an array — with no pointers at all

Because a heap is always complete, you don't need any pointers; the whole tree fits in a flat array. For 0-indexed arrays:

• parent of i = (i-1)/2
• left child = 2i+1, right child = 2i+2

// Min-heap sift operations, array-backed.
void siftUp(int[] h, int i) {              // after inserting at the end
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h[i] >= h[p]) break;           // parent already smaller -> done
        swap(h, i, p);
        i = p;
    }
}
void siftDown(int[] h, int i, int size) {  // after removing root (moved last elem to root)
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, smallest = i;
        if (l < size && h[l] < h[smallest]) smallest = l;
        if (r < size && h[r] < h[smallest]) smallest = r;
        if (smallest == i) break;
        swap(h, i, smallest);
        i = smallest;
    }
}

You call siftUp after inserting at the end: bubble the newcomer up until it's no smaller than its parent. You call siftDown after removing the root: move the last element to the top and sink it until the heap property holds.

Java's PriorityQueue

java.util.PriorityQueue is a binary min-heap by default (natural ordering), unbounded, array-backed. Pass a Comparator to change the ordering. A few critical caveats every senior must know:

• offer/poll are O(log n); peek is O(1).
• remove(Object) and contains(Object) are O(n) — they linear-scan, because a heap isn't searchable by value.
• Iteration order is NOT sorted. for (x : pq) walks the backing array in arbitrary heap order. Only repeated poll() yields sorted output.
• It is not thread-safe; use PriorityBlockingQueue for concurrency.
• Duplicates are allowed; null is not.

// Max-heap: reverse comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// k-th LARGEST element: keep a size-k MIN-heap of the largest-so-far.
int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min-heap
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll(); // evict smallest -> heap holds top k
    }
    return minHeap.peek();  // smallest of the top-k = k-th largest. O(n log k)
}

Java has PriorityQueue-based patterns for other classics too: top-K frequent, merge k sorted lists, and median of a stream (using two heaps — a max-heap for the lower half and a min-heap for the upper half).

Tries (prefix trees)

A trie is an m-ary tree keyed by the characters of strings; the path from root to a node spells a prefix. Tries give O(L) insert/search where L is the key length — independent of how many keys are stored — and, crucially, native prefix queries: autocomplete, longest-prefix match (routing tables), spell-check, IP lookup.

class Trie {
    static class Node {
        Node[] next = new Node[26];   // fixed alphabet a-z; use HashMap<Character,Node> for Unicode
        boolean isWord;
    }
    private final Node root = new Node();

    void insert(String w) {
        Node cur = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (cur.next[i] == null) cur.next[i] = new Node();
            cur = cur.next[i];
        }
        cur.isWord = true;            // mark terminal
    }

    boolean search(String w) { Node n = find(w); return n != null && n.isWord; }
    boolean startsWith(String p) { return find(p) != null; }

    private Node find(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (cur.next[i] == null) return null;
            cur = cur.next[i];
        }
        return cur;
    }

    // Autocomplete: collect all words under the prefix node.
    List<String> autocomplete(String prefix, int limit) {
        List<String> res = new ArrayList<>();
        Node start = find(prefix);
        if (start != null) dfs(start, new StringBuilder(prefix), res, limit);
        return res;
    }
    private void dfs(Node n, StringBuilder path, List<String> res, int limit) {
        if (res.size() >= limit) return;
        if (n.isWord) res.add(path.toString());
        for (char c = 'a'; c <= 'z'; c++) {
            Node child = n.next[c - 'a'];
            if (child != null) {
                path.append(c);
                dfs(child, path, res, limit);
                path.deleteCharAt(path.length() - 1); // backtrack
            }
        }
    }
}

Classic problems

Validate a BST (the #1 gotcha)

// WRONG naive attempt only checks node vs immediate children — misses violations
// across subtrees. Correct: carry down (min, max) bounds.
boolean isValidBST(TreeNode n, long min, long max) {
    if (n == null) return true;
    if (n.val <= min || n.val >= max) return false;      // must be strictly within bounds
    return isValidBST(n.left, min, n.val)                // tighten upper bound
        && isValidBST(n.right, n.val, max);              // tighten lower bound
}
// call: isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)

The idea: instead of comparing a node only against its immediate children, you carry a permitted range (min, max) down as you descend, tightening it. Go left and the ceiling becomes the current node's value; go right and the floor does.

Lowest Common Ancestor

For a BST, exploit the ordering — O(height):

TreeNode lcaBST(TreeNode n, int p, int q) {
    while (n != null) {
        if (p < n.val && q < n.val)      n = n.left;   // both smaller -> go left
        else if (p > n.val && q > n.val) n = n.right;  // both larger -> go right
        else return n;                                 // split point = LCA
    }
    return null;
}

The idea: the first node where p and q fall on opposite sides (or one of them is the node itself) is the lowest common ancestor.

For a general binary tree (no ordering), recurse and find where the two targets split:

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode l = lca(root.left, p, q);
    TreeNode r = lca(root.right, p, q);
    if (l != null && r != null) return root;   // p and q found in different subtrees
    return l != null ? l : r;                  // both on one side (or neither)
}

Serialize / deserialize (pre-order with null markers)

static final String NULL = "#", SEP = ",";

String serialize(TreeNode n) {
    StringBuilder sb = new StringBuilder();
    ser(n, sb);
    return sb.toString();
}
void ser(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append(NULL).append(SEP); return; }
    sb.append(n.val).append(SEP);
    ser(n.left, sb);
    ser(n.right, sb);
}
TreeNode deserialize(String data) {
    Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(SEP)));
    return deser(q);
}
TreeNode deser(Deque<String> q) {
    String t = q.poll();
    if (NULL.equals(t)) return null;
    TreeNode n = new TreeNode(Integer.parseInt(t));
    n.left  = deser(q);   // pre-order: left subtree consumed first
    n.right = deser(q);
    return n;
}

Common pitfalls

• Recursion depth: deep/skewed trees blow the stack. Know the iterative forms.
• BST duplicates: decide your policy (reject, count, or lean-left/right consistently) — an inconsistent rule silently corrupts search.
• == vs .equals in a tree of objects: identity-vs-value comparison bugs.
• Integer overflow in isValidBST bounds and in (lo+hi)/2 midpoints elsewhere.
• PriorityQueue iteration is unordered — a top source of "why is my output wrong" bugs.
• Comparator inconsistency with equals breaks TreeMap/TreeSet — two keys that compare 0 are treated as equal regardless of equals, so a bad comparator can silently drop entries.
• Heap remove(Object) is O(n) — don't build a Dijkstra on it naively; use decrease-key patterns or lazy deletion.

Best practices

• Reach for TreeMap/TreeSet when you need ordered iteration, floor/ceiling/higher/lower, or range views — not just membership (use HashMap for that).
• Use PriorityQueue for streaming top-K, scheduling, Dijkstra/Prim, and merge problems. For the top-K-largest pattern, remember the size-k min-heap trick.
• Use a trie only when you genuinely need prefix operations; otherwise a HashMap is simpler and often faster for exact-match.
• For persistent/on-disk ordered data, it's B+ trees under the hood — understand fan-out and leaf-linking even if you never implement one.
• Prefer iterative traversals in library/production code where input depth is untrusted.

Interview Questions

boolean bad(TreeNode n){ if(n==null) return true;
  if(n.left!=null && n.left.val>=n.val) return false;
  if(n.right!=null && n.right.val<=n.val) return false;
  return bad(n.left)&&bad(n.right); }

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,1,3,2,4));
System.out.println(pq);   // ?