Stage 4·Trees & BSTs

Balance, Heaps & Tries

Why balance matters (and what a self-balancing tree buys you), how a heap is a tree in an array, and the trie for prefix problems.

14 min readAdvanced

On this page

Two more tree structures round out the interview toolkit: the heap, a tree cleverly stored in an array that always gives you the extreme value, and the trie, a tree of characters built for prefix problems. Plus a closer look at why balance matters enough that whole categories of trees exist to maintain it.

Balance, and self-balancing trees

You've seen that a BST's O(log n) promise depends on balance, and that sorted insertions ruin it. Self-balancing trees - AVL and red-black - fix this by performing rotations during insertion and deletion: small, local restructurings that keep the height within a constant factor of log n. You rarely implement these in an interview, but you should be able to say why they exist (to guarantee O(log n) regardless of insertion order) and that Java's TreeMap/TreeSet are red-black trees.

A heap is a tree in an array

A binary heap is a complete binary tree with a simple property: every parent is smaller than its children (a min-heap) or larger (a max-heap). The clever part: because it's complete, it's stored in a plain array with no pointers - a node at index i has children at 2i+1 and 2i+2:

min-heap:        1              array: [1, 3, 2, 7, 4, 5]
               /   \            index:   0  1  2  3  4  5
              3     2           children of i: 2i+1, 2i+2
             / \   /            parent of i:   (i-1)/2
            7   4 5

This gives you the minimum (or maximum) at the root in O(1), with insertion and removal in O(log n) as elements "bubble" up or down. Java's PriorityQueue is a binary heap - the go-to for top-k, "process the smallest next," and merge-k problems from the heaps module.

The trie: a tree of prefixes

A trie (prefix tree) stores strings by sharing their common prefixes along tree paths. Each node represents a character; a path from the root spells a prefix; a flag marks where complete words end:

class TrieNode {
    TrieNode[] children = new TrieNode[26];   // one slot per letter
    boolean isWord;
}
// insert "cat": root → c → a → t (mark isWord). "car" shares c → a, then branches to r.

Tries make prefix queries fast: "does any word start with 'ca'?" or autocomplete is a walk down the trie in O(length), independent of how many words are stored. They're the right answer whenever a problem is about shared prefixes or word lookups.

Recognize the structure from the problem

'K largest / smallest,' 'merge sorted streams,' 'running median' → heap. 'Autocomplete,' 'words with a common prefix,' 'search a dictionary of words' → trie. 'Sorted keys with range/floor/ceiling queries' → balanced BST (TreeMap). Naming the structure the problem implies is often the whole insight.

A heap as a corporate tournament bracket

Picture a knockout tournament where the rule is 'a manager always outranks their direct reports.' The overall champion (the extreme value) is always at the very top, instantly available. When someone new joins, they start at the bottom and are promoted upward past any report they outrank until they sit in the right spot - that's the O(log n) 'bubble up.' The whole bracket is regular enough to write on a single numbered list (the array), with each position's reports at fixed offsets - no org-chart lines needed. That's a binary heap: a tree so complete it lives in an array.

Why a heap, not a sorted list, for a priority queue

You need a structure that repeatedly gives you the smallest element and lets you insert new elements, both efficiently. Compare a min-heap against keeping a sorted ArrayList, and say which wins and why.

How is a binary heap stored, and what does it give you in O(1)?

Key takeaways

Self-balancing trees (AVL, red-black) rotate on insert/delete to keep height O(log n) regardless of input order; TreeMap/TreeSet are red-black.
A binary heap is a complete tree stored in an array (children at 2i+1, 2i+2), giving the min/max at the root in O(1) and O(log n) insert/remove.
Java's PriorityQueue is a heap - use it for top-k, 'smallest next', running median, and merge-k problems.
A trie stores strings by shared prefixes, making prefix queries and autocomplete O(word length).
Recognizing which specialized tree a problem implies (heap, trie, balanced BST) is often the key insight.

Was this lesson helpful?

Edit this page on GitHub