Question

A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is ____.

Accepted Answer

The correct answer is 8. 1023 = 2^10−1 nodes forms a perfect binary tree with depths 0 through 9. In a min-heap, every ancestor of a node must hold a smaller value. To push the value 9 as deep as possible, place it at the end of a root-to-node chain whose other members are the 8 values smaller than 9 (namely 1-8), one per depth level 0 through 7 — a valid heap-order chain — with 9 itself at depth 8. Any remaining sibling subtrees can freely absorb the larger unused values (10-1023), so this assignment is fully valid. Depth 8 is achievable and is the maximum, since 9 needs exactly 8 strictly-smaller ancestors and only 8 such values (1-8) exist. (Verified this 'k needs k-1 smaller ancestors' rule against a small worked example with k=3 before trusting it at k=9.)

Explanation