Trie & Heap Problems

Seven classic interview problems — Implement a Trie, Add and Search Words with a wildcard, Kth Largest Element in a Stream, Last Stone Weight, K Closest Points to the Origin, Task Scheduler and Find Median from a Data Stream — solved from zero with two tree-shaped tools. A trie stores words letter by letter so that "is there a word starting with ca?" costs only two steps. A heap hands you the smallest (or largest) item of a changing collection in O(log n). Dart ships neither as a ready-made class for this job, so you will write a small, tested BinaryHeap first and reuse it all the way down the page. For every problem you get the slow obvious idea, the trick that fixes it, the pseudocode, the Dart code, and an animation you can feed your own input — the trie drawn as a tree of letter nodes, the heap drawn both as a tree and as the list that really stores it.

Tries, heaps and the patterns they unlock

Some words first, because both tools are trees:

• A tree is a set of boxes called nodes, joined by lines. One node at the top is the root. Each node can have children below it; the node above a child is its parent. A node with no children is a leaf. Computer trees grow downwards: the root is drawn at the top.
• A binary tree is a tree where every node has at most two children, called left and right. The full story of trees, with drawings, is in C10 · Representing rooted trees, and the next problem set (Step 13.7 · Tree Problems) practises them on their own.
• A prefix of a word is its beginning: c, ca and car are prefixes of card. A word is also a prefix of itself.
• O(L) means "work that grows with the length L of one word"; O(log n) means "work that grows like the number of times you can halve n" — about 20 steps for a million items. See C03 · Growth of Functions.

What a trie is

A trie (say "try", from retrieval) is a tree of letters. The root stands for the empty prefix. Each child is reached by one letter, so the path from the root down to any node spells a prefix. Words that start the same way share the same nodes: car and cat share the nodes for c and a, and split only at the last letter. Because a path can stop in the middle of a longer word (car inside card), every node carries one extra flag, isEnd: "a stored word ends exactly here". In the animations, that flag is drawn as a purple ring around the node.

Three operations, each walking one letter per step:

• insert(word): walk down letter by letter, creating any missing child, then switch on isEnd at the last node — O(L).
• search(word): walk down; if a letter is missing, the word is not there; if the walk finishes, the answer is the last node's isEnd — O(L).
• startsWith(prefix): the same walk; if it finishes at all, some stored word starts with the prefix — O(L).

None of the three depends on how many words are stored. A Set<String> also finds a whole word quickly (by hashing it — D27 · HashSet and HashMap inside), but a set cannot answer "does any word start with ca?" without looking at every word. That prefix question is what tries are for: autocomplete, spell checkers, word games and routing tables.

What a heap and a priority queue are

A priority queue is a collection where items come out in order of priority, not in order of arrival: push adds an item, pop removes the item with the best priority, and peek looks at it without removing it. "Best" is your choice: the smallest number, the largest number, the closest point, the most urgent patient.

A binary heap is the usual way to build one. It is a binary tree with two rules:

1. Shape rule: the tree is filled level by level, left to right, with no gaps. Thanks to this rule the tree fits perfectly into a plain list: the root is at index 0, and the children of index i are at 2i + 1 and 2i + 2; the parent of index i is at (i − 1) ~/ 2 (~/ is Dart's whole-number division). No arrows are stored at all — the positions are the arrows.
2. Heap rule: every parent comes out before its children. In a min-heap every parent is ≤ its children, so the smallest item sits at the root, index 0. In a max-heap every parent is ≥ its children, so the root holds the largest. The heap is not sorted — siblings can be in any order — and that is exactly why it is cheaper to keep up than a sorted list.

Both operations repair the heap rule along one path from a leaf to the root, and a tree of n items filled level by level is only about log₂ n levels tall:

• push puts the new item in the first free spot (the end of the list), then sifts it up: while it beats its parent, swap the two. O(log n).
• pop takes the root, moves the last item into the root's place, then sifts it down: while one of its children beats it, swap it with the better of the two children. O(log n).
• peek reads index 0. O(1).

Heaps, heapsort and priority queues are built step by step in C06 · The binary heap as an array and C06 · Priority queues. Here we only need a small, reliable one.

Dart has no built-in heap — so write one

Look through dart:core and dart:collection: there are lists, sets, maps, queues and linked lists, but no priority queue. (The separate collection package from pub.dev has HeapPriorityQueue, but interview pads usually run plain Dart without packages.) So here is a small generic one. The type parameter T means it can hold anything — numbers, points, records — and the function compare decides the order: compare(a, b) < 0 means "a must come out before b". Generics are explained in D10 · Generics. The verification program for this page pushes and pops it hundreds of times against a sorted list, checks the heap rule after every step, and drains it to confirm the output is sorted.

The pseudocode below is the same two procedures. "Better" means "comes out first": smaller for a min-heap, larger for a max-heap. Type your own pushes and pops and watch every comparison; the tree and the list under it always show the same items.

An edge case: a max-heap with repeated values. Watch the second 9: it is equal to its parent, and equal is not better, so it stops — ties never cause a swap. Popping then hands out the two 9s one after the other.

Min-heap or max-heap? Only the comparator changes

The same class gives both kinds. Pass (a, b) => a.compareTo(b) for a min-heap and (a, b) => b.compareTo(a) — the two swapped — for a max-heap. For records (two values bundled together, D11 · Records) you can compare by one field and break ties by another, so the order is always fully decided:

When you do not need a heap

Amortized means "on average over a long run of operations": a single splay-tree step can be slow, but a long sequence never is. A SplayTreeMap keeps one entry per key, so to store repeated values you count copies in the map's value:

Pattern 1: keep the k best in a heap of size k

To keep the k largest values of a long stream, use a min-heap — it sounds backwards, so slow down here. The heap holds your current top k. Its root is the weakest member of that top k. When a new value arrives, push it; now there are k + 1 values, and the smallest of them (the root) cannot be in the top k any more, so pop it. The root is then exactly the k-th largest value seen so far. Memory stays O(k) no matter how long the stream is, and each value costs O(log k). For the k smallest values, flip everything: a max-heap of size k whose root is the largest of the small ones.

Kth Largest in a Stream and K Closest Points below are this pattern; so are the "top k" questions in the bank. It is the heap cousin of Step 13.1 · Top K Frequent Elements.

Pattern 2: two heaps that meet in the middle

To know the middle of a changing collection, split it into a lower half and an upper half. Keep the lower half in a max-heap (its root is the largest of the small numbers) and the upper half in a min-heap (its root is the smallest of the big numbers). The two roots face each other across the middle, so the median is one root or the average of both. After every insert, move one root across if the halves differ in size by more than one. Find Median from a Data Stream below builds this step by step; the same idea solves the sliding-window median and the "maximize capital" question in the bank.

Implement a Trie

The task. Build a class Trie with three methods: insert(word) stores a word; search(word) says whether exactly that word was stored; startsWith(prefix) says whether at least one stored word begins with prefix. Words use the lowercase letters a to z.

Brute force. Keep the words in a plain Dart List. search compares the word with every stored word; startsWith checks w.startsWith(prefix) for every word. Each call is O(n · L) for n stored words of length L — fine for ten words, hopeless for thirty thousand.

Key insight. Words that share a beginning should share the work. Store the words as paths in a tree where each step is one letter: then a search reads each letter of the query once, and the number of stored words never enters the cost. One node type is enough: a map from the next letter to the child node, and the flag isEnd.

Why the flag is needed. After inserting only "car", the path c → a exists, but "ca" was never inserted. The path alone cannot tell "a word ends here" from "a word passes through here". So search asks two things — does the path exist, and is isEnd on at its last node — while startsWith asks only the first.

Dart details: putIfAbsent(letter, TrieNode.new) returns the existing child, or creates one with the constructor tear-off TrieNode.new and stores it — one lookup instead of a check and an insert. word[i] is the one-letter String at index i. _walk(word)?.isEnd ?? false reads "if the walk found a node, its flag; otherwise false" (D05 · Null Safety).

Type your own operations. Each word is inserted letter by letter; new nodes appear in red, shared nodes are reused; queries walk down and stop either at a missing letter or at the last node. Children are drawn in the order they were added — the same order in which Dart's map stores them.

An edge case: an empty trie, then a word that is also a prefix of a longer word. search("go") fails before anything is stored, succeeds once "go" is stored — and keeps succeeding after "gone" is added, because "gone" only extends the path below the marked node.

Complexity. Every call is O(L) for a word or prefix of length L — one map lookup per letter. Memory is O(total letters) in the worst case (no shared prefixes), and less when words share beginnings. Each node is an object with its own map, so a trie of a million short words uses noticeably more memory than a Set<String> of them.

Follow-ups interviewers ask. Count how many stored words start with a prefix, and support erasing a word (p08-q21: keep a counter in each node). Delete a word and free the nodes nobody needs any more (p08-q29). Replace the map with a fixed list of 26 children for speed — List<TrieNode?>.filled(26, null), indexed by codeUnitAt(i) - 97 — trading memory for speed. Suggest the three smallest words for every typed prefix (p08-q17).

The idea underneath: rooted trees with any number of children (C10 · Representing rooted trees) and maps (D27 · What a Set and a Map really are).

Add and Search Words with a wildcard

The task. Build a WordDictionary with addWord(word) and search(pattern). A pattern is made of lowercase letters and dots; a dot . stands for exactly one letter, any letter. search returns true if some stored word has the same length as the pattern and matches it letter by letter.

Brute force. Keep the words in a list; for a search, compare the pattern with every word of the same length, treating a dot as "anything". O(n · L) per search.

Key insight. Store the words in a trie exactly as before. A normal letter in the pattern still picks one child. A dot picks every child in turn: call the same search on each child for the rest of the pattern, and stop at the first one that succeeds. The function calls itself (recursion — D07 · Functions and the Call Stack), and each call remembers where it was, so returning from a failed branch automatically brings us back to try the next child.

Why it is correct. _match(node, pattern, i) answers one precise question: "can the letters from position i onward be read along some path that starts at node and ends at a node marked isEnd?" When i reaches the end of the pattern, the answer is that node's flag. A letter has only one way forward; a dot has one way per child, and the answer is true if any of them works. Trying every child covers every word that could match, so nothing is missed.

An edge case: an empty dictionary, then words of different lengths. A dot must use up a real letter, so "..." fails even though "ab" matches the first two dots — the third dot finds no child below b.

Complexity. addWord: O(L). search without dots: O(L). With dots, the walk can branch at each dot into up to 26 children, so the worst case is O(26^d · L) for d dots — and never more than the number of nodes in the trie. Space: O(total letters stored), plus O(L) for the recursion.

Follow-ups interviewers ask. Find every word from a list that can be traced on a letter grid (p08-q22: a trie plus backtracking on the grid — the grid search itself is practised in Step 13.12 · Backtracking Problems). Support * for "any run of letters" (the dot loop plus a "skip this node" branch). Return all matches, not just true or false (collect instead of stopping at the first success).

The idea underneath: the trie from the problem above, and recursion that undoes its choice when a branch fails (D07 · Functions and the Call Stack).

Kth Largest Element in a Stream

The task. Build a class KthLargest(k, nums) that starts with the numbers in nums. Its method add(val) adds one more number and returns the k-th largest number seen so far (counting repeats separately: in 9, 7, 7 the second largest is 7). After every add there are at least k numbers.

Brute force. Keep every number in a sorted list. Each add finds the place for the new number and shifts the rest — O(n) — then reads the k-th element from the end. Simple and correct, but n keeps growing with the stream.

Key insight. Numbers below the current top k can never matter again: the top k only ever gets better. So keep only the k largest numbers, in a min-heap. Its root is the smallest of the k largest — which is, by definition, the k-th largest. That is Pattern 1 from the opening: push, and if the heap now holds k + 1 numbers, pop the root.

Why it is correct. The invariant (a fact that stays true after every step): the heap holds exactly the k largest numbers seen so far (fewer while fewer than k have arrived). Adding x and then removing the smallest of the k + 1 numbers leaves the k largest of the old top k plus x — and any number outside the old top k was already beaten by k others, so it cannot be in the new top k either.

An edge case: k = 1 with a repeated value. The heap holds one number — the maximum so far. The second 4 is pushed and then one of the two 4s is popped; the answer stays 4.

Complexity. Each add is one push and at most one pop on a heap of at most k + 1 items: O(log k). The constructor costs O(n log k) for n starting numbers. Space: O(k) — the rest of the stream is forgotten.

Follow-ups interviewers ask. The k-th largest of a fixed array: the same heap, or quickselect in O(n) expected time (p08-q7 and p08-q15). The k largest items by some score with ties broken by name (p08-q12). The stream is so large it does not fit in memory: the heap still needs only k numbers.

The idea underneath: Pattern 1 above, the priority queue of C06 · Priority queues, and selection without full sorting in C09 · randomizedSelect.

Last Stone Weight

The task. You have stones with positive whole-number weights. Repeatedly take the two heaviest and smash them together: if their weights are equal, both are destroyed; otherwise the lighter one is destroyed and the heavier one loses that much weight and stays. Stop when at most one stone is left, and return its weight, or 0 if none is left.

Brute force. Sort the stones, take the last two, put back the difference, and sort again. Each round costs O(n log n) and there are up to n rounds: O(n² log n).

Key insight. Every round needs the two largest values of a collection that changes by one item at a time — that is a priority queue. Put all stones in a max-heap; pop twice to get the heaviest y and the second heaviest x; if y > x, push y − x back. Each smash removes at least one stone, so the loop runs at most n − 1 times.

An edge case: every smash destroys both stones. The heap ends empty, and the answer is 0 — the code must not call peek on an empty heap.

Complexity. Building the heap with n pushes is O(n log n) (building it bottom-up from the whole list is O(n) — p08-q28). At most n − 1 smashes, each O(log n): O(n log n) time, O(n) space for the heap.

Follow-ups interviewers ask. Join sticks where each join costs the sum of the two lengths, as cheaply as possible (p08-q13 — the two smallest each time, a min-heap, the same greedy as Huffman coding in C16 · Huffman codes). Choose which stones to smash to make the last stone as light as possible — a different problem that needs dynamic programming, not a heap.

The idea underneath: a max-heap as a priority queue (C06 · Priority queues) and the comparator trick from the opening.

K Closest Points to the Origin

The task. You get a list of points on a grid, each written [x, y] with whole numbers, and a number k. Return the k points closest to the origin (0, 0), measuring straight-line distance √(x² + y²). Any order is accepted; this page returns them closest first. When two points are equally far, either may be chosen.

Brute force. Sort all points by distance and take the first k. O(n log n) time — perfectly acceptable here, and the reference this page's tests use.

Key insight. This is Pattern 1 with the order flipped: we want the k smallest distances, so keep a max-heap of size k. Its root is the farthest of the points kept; when a (k + 1)-th point arrives, that root is the one point that surely does not belong, so pop it. Two more details: compare squared distances x² + y² — the square root does not change which point is nearer, and leaving it out keeps everything in exact whole numbers; and at the end, popping gives the farthest first, so reverse.

In the animation, the plane on the left shows every point; the heap on the right holds the points kept so far, ordered by squared distance (written under each point). Type your own points and k.

An edge case: k equals the number of points. The heap never grows past k, so nothing is ever popped during the loop — every point is kept, and the final pops only put them in order.

Complexity. n pushes and at most n pops on a heap of at most k + 1 points: O(n log k) time, O(k) space. Quickselect on the distances finds the k closest in O(n) expected time without a heap, but needs the whole list in memory.

Follow-ups interviewers ask. The points arrive one at a time and you must always know the k closest (the same heap, kept open). The k closest values to a target in a sorted array (binary search, then two pointers — Step 13.5 · Binary Search). The k-th smallest value in a sorted matrix (p08-q20).

The idea underneath: Pattern 1 above, comparators on lists (D26 · List methods), and selection in C09 · randomizedSelect.

Task Scheduler

The task. A machine runs tasks, one per time slot. Each task is a capital letter, and the same letter may appear many times. After running a task, the machine must wait at least n slots before running the same letter again; in between it can run other letters or stay idle. Tasks may run in any order. Return the smallest number of slots needed to finish all tasks, idle slots included.

Brute force. Try every order of the tasks; for each order, place each task in the earliest slot its cooldown allows, and keep the shortest total. The number of orders explodes (12 tasks already have hundreds of thousands of distinct orders), so this only serves as a reference for tiny inputs — the verification program uses it on 400 random small cases.

Key insight 1 — the greedy simulation. Work in rounds of n + 1 slots. Inside one round every letter can appear at most once (a letter used at the start of a round is cooled down by the start of the next). So in each round, run up to n + 1 different letters, always choosing those with the most runs left — a max-heap of counts. Letters that still need runs go back into the heap after the round. A round that could not be filled leaves idle slots — except the very last round, which simply stops.

Why "most runs left first" is right. The letter with the most remaining runs is the one that will force idle slots at the end if it falls behind; running it as early as possible spreads its copies out. Using a letter with fewer runs instead never helps, because the two choices can be swapped without breaking any cooldown.

Key insight 2 — the counting formula. Let maxCount be the count of the most frequent letter and tied the number of letters that share that count. Lay the most frequent letter out as maxCount rows, each row n + 1 slots wide: the first maxCount − 1 rows are full width (the letter, then its cooldown), and the last row holds only the tied letters. That frame has (maxCount − 1) · (n + 1) + tied slots, and every other letter fits into its gaps. If there are more tasks than gaps, the rows just get longer with no idle slots at all, and the answer is simply the number of tasks. So the answer is max(tasks.length, (maxCount − 1) · (n + 1) + tied).

An edge case: more letters than gaps. The formula's frame gives (2 − 1) × (1 + 1) + 3 = 5, but there are 7 tasks, so the answer is 7 — and the simulation never inserts an idle slot.

Complexity. Simulation: each run of a task is one pop and at most one push on a heap of at most 26 counts, so O(T log 26) = O(T) time for T tasks (plus up to n idle slots per round). Formula: one counting pass, O(T). Both use O(26) = O(1) extra space.

Follow-ups interviewers ask. Return an actual schedule, not just its length (record the letters as the simulation runs). Rearrange a string so no two equal letters touch (p08-q16 — the same heap with n = 1). The tasks must run in the given order (a different problem: a map from letter to the last time it ran, no heap). Prove the formula (p08-q32).

The idea underneath: a greedy choice that never needs undoing (C16 · Elements of the greedy strategy) and a max-heap of counts, the counting idea of Step 13.1 · Top K Frequent Elements.

Find Median from a Data Stream

The task. Build a MedianFinder with addNum(num), which adds a whole number, and findMedian(), which returns the median of all numbers added so far as a double. The median is the middle value once the numbers are sorted; with an even count it is the average of the two middle values. findMedian is only called after at least one addNum.

Brute force. Keep a list and sort it whenever the median is asked: O(n log n) per question. Keeping the list sorted on every insert is O(n) per insert instead.

Key insight. The median only depends on the one or two numbers in the middle. Pattern 2 from the opening keeps exactly those in reach: low, a max-heap of the smaller half, and high, a min-heap of the larger half. Two invariants hold after every addNum: every number in low is ≤ every number in high, and low holds as many numbers as high or exactly one more. Then the median is low's root (odd count) or the average of both roots (even count).

How an insert keeps both invariants. A new number goes into low if it is ≤ low's root (it belongs to the smaller half), otherwise into high — this keeps the order invariant. Then, if low is two bigger, move its root (the largest small number) into high; if high is bigger, move its root (the smallest large number) into low. Moving a root across keeps the order invariant too, because the root is the number closest to the other side.

An edge case: repeated negative numbers. Equal numbers go to low (the test is ≤), and rebalancing moves one across when low runs two ahead. The median stays −3.0 throughout.

Complexity. addNum: one push and at most one pop-and-push, O(log n). findMedian: one or two peeks, O(1). Space: O(n) — every number is kept, split between the two heaps.

Follow-ups interviewers ask. All numbers are between 0 and 100: count them in 101 buckets instead, O(1) per insert (p08-q31). 99% of the numbers are in that range: buckets plus two small heaps for the outliers. The median of a sliding window of the last k numbers: two heaps plus delayed removal (p08-q25). The median of two sorted arrays: a binary search, not a heap (Step 13.5 · Median of Two Sorted Arrays).

The idea underneath: Pattern 2 above, the median and order statistics of C09 · Order statistics, and the heap of C06 · The binary heap as an array.

Quiz

Interview questions

Variations and follow-ups of the seven problems above — top-k questions, merging, scheduling, tries with counters and deletion, and the two-heaps trick on harder inputs. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow but obviously correct reference (sorting, scanning every word, or trying every choice).

Cheat sheet

Heaps are not sorted — only the root is guaranteed. Tie-breaks belong in the comparator, priorities belong inside the item, and an empty heap has no peek. In a trie, the path says "a word passes here"; only isEnd says "a word ends here".