A teammate wants an in-order walk of a max-heap to list ratings descending — why does that fail?
answer
- a traversal reveals only stored relations
- which pairs does a heap never compare?
- left subtree versus right subtree — unconstrained
- the root prints mid-sequence, dominating both sides
- ordered output means draining, O(n log n)
basics
~20 sThe heap invariant relates a node only to its own children, never one subtree to another, so an in-order walk emits an arbitrary sequence. Ranked output costs O(n log n) by removing the root n times.
solid answer
~50 sA traversal can only reveal an order the structure actually stores, and a heap stores one relation: node versus its own two children. Nothing ranks the left subtree against the right, so an in-order walk visits the left subtree, then the node, then the right subtree, producing a sequence with no ordering guarantee at all — the node it prints in the middle is larger than everything in *both* halves, which is exactly not what in-order output means. Concretely, walking `[90, 70, 85, 40, 65, 80, 50]` in order emits 40, 70, 65, 90, 80, 85, 50. What a heap genuinely offers is the extreme in O(1) and full descending output only by removing the root n times, O(n log n), which drains the structure unless you copy it first. If the workload needs ordered iteration *and* extreme access, say so at design time and pick a structure that maintains a total order, or keep a second index.
code
pseudocode · 12 lines// ratings[0..n-1] is a valid max-heap
// e.g. [90, 70, 85, 40, 65, 80, 50]
inorder(i):
if i >= n:
return
inorder(2*i + 1)
visit(ratings[i])
inorder(2*i + 2)
inorder(0)
// visits: 40, 70, 65, 90, 80, 85, 50go deeper
Remember the one-line rule: a heap orders a node against its own children only, so no walk of it comes out sorted. The array is not a ranked list.
Trace a small max-heap in-order and show the root landing in the middle of values it dominates, then state that ordered output costs O(n log n) by repeated removal.
Turn it into a design conversation: identify which access path is actually hot, and say when the heap is the wrong primary structure versus when a partial drain of a copy is the right fix.
Own the call between one structure that serves the hot path and two views kept consistent, and make the staleness and maintenance cost of the second view explicit before it is discovered in production.
## The general principle **A traversal can only recover an order the data structure paid to maintain.** A heap pays for exactly one relation — each node versus its own two children — and it pays as little as possible for it, because that is what keeps repairs to a single root-to-leaf path. Any question of the form "can I read this structure out in sorted order?" reduces to "does the structure constrain the pairs I would need compared?" For a heap the answer is no for every pair that is not a parent-child edge. ## Tracing the walk Take a matchmaking pool as a max-heap: `[90, 70, 85, 40, 65, 80, 50]`, 0-indexed. As a tree the root is 90; its children are 70 and 85; 70's children are 40 and 65; 85's children are 80 and 50. Every parent dominates its children, so it is valid. An in-order walk (left subtree, node, right subtree) visits: 40, 70, 65, **90**, 80, 85, 50. That is not descending, not ascending, and not close to either. Notice the structural reason it *cannot* be: in-order output puts the node between the two subtrees, which only means something if everything on the left precedes it and everything on the right follows. In a heap the node is the largest of all three parts, so it lands in the middle of a sequence it dominates. The traversal is well-defined; the ordering claim attached to it is not. Pre-order and post-order fare no better. Pre-order at least starts with the maximum — the root — and never breaks the rule that a node precedes its descendants, so it is a valid *topological* order of the domination relation. It still says nothing about the relative rank of two nodes on different branches, so 80 may print before or after 70 depending only on layout. Level order, which is just reading the array left to right, has the same property: each level's minimum is >= nothing in particular relative to the next level's maximum. ## What you can actually get, and what it costs - **The extreme, O(1).** Read index 0. This is the entire point of the structure. - **All n elements in descending order, O(n log n).** Remove the root n times; each removal repairs one path. This drains the heap, so if the pool must survive, copy it first — and once you are copying and spending O(n log n), a general sort of the copy is an equally valid choice with better constants for a one-off report. - **An arbitrary element by key, O(n).** Since no comparison directs the search, you scan. This surprises people who expect tree-shaped structures to support O(log n) lookup; the shape is a tree but the ordering is not a search ordering. - **The k largest, O(n + k log n)** starting from an existing max-heap, or O(n log k) by streaming through a size-k min-heap. Both beat a full sort when k is small — and this is the genuine reason to reach for a heap over a sorted list in the first place. ## Reviewing the proposal When a colleague proposes the in-order walk, the productive response is not "heaps do not work that way" but a question about the requirement. If the leaderboard genuinely needs the full pool in rank order on every request, the heap is the wrong primary structure for that access path — a structure maintaining a total order gives O(n) iteration, and the heap's advantage over it (cheaper insert, O(1) peek) is not being used. If instead the request needs the **top few** and the pool churns constantly, the heap is exactly right and the fix is a partial drain of a copy, not a traversal. If both access paths are hot, the honest answer is two structures over the same records, with the cost of keeping them consistent stated openly rather than discovered later. ## The misconception to name The underlying error is importing a rule from search-ordered trees, where each node separates its subtrees by key so an in-order walk is sorted. A heap deliberately does not maintain that stronger property, and the weakness is the source of its speed: maintaining a subtree-wide ordering after an insertion costs more than the single-path repair a heap needs. Two structures can share the same tree shape and offer completely different guarantees; the shape is not the contract.
- Does any traversal of a heap produce a useful order?Pre-order and level order both guarantee that a node appears before its descendants, so each is a valid topological order of the domination relation and each starts with the extreme. Neither ranks nodes on different branches, so neither is sorted. If you need sorted output, you must spend the comparisons the structure never made.
- How expensive is finding one specific rating in a heap of n records?O(n). Comparisons only relate a node to its children, so no branch can be eliminated at any step — unlike a search-ordered structure, there is no direction to follow. You can prune slightly in a max-heap when the target exceeds the current node, since no descendant can be larger, but the worst case stays linear.
- The team needs both the top few and full rank order on demand. What do you propose?Serve the hot path from the heap and build the ranked view separately — a sorted copy produced on demand, or a second structure maintaining a total order, refreshed on a cadence the product can tolerate. State the consistency cost of two views up front; the failure mode people accept accidentally is a ranked view that silently lags the pool.
saying these in an interview costs you the question
- Assumes in-order traversal of any tree yields sorted output
- Claims heap search costs O(log n) like a search tree
- Says reading the array left to right gives ranked order
- Forgets that draining a heap for order destroys it
- Treats tree shape as if it implied the ordering contract