Structure and Measure

What is this?

Sometimes you don't want to change a tree, you just want to understand its shape. Is it neatly filled in, level by level, like seats packed into a theatre row? How few steps to the nearest exit? Where do two people's family lines first meet? These problems are about reading those facts off a tree, and the trick is picking the right way to walk it — sweeping across levels for layout questions, or going deep so each node can hear back from its children.

💡 Fun fact: A "complete" binary tree — one filled level by level with no gaps — is the secret backbone of the heap, the data structure that powers priority queues. That tidy gap-free shape lets the whole tree be stored in a plain flat array with no pointers at all.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Before you can transform a tree, you have to read it. This bucket is about extracting facts from a binary tree's shape: is it filled in level by level, how shallow is its nearest leaf, and where do two nodes' paths first join. Two tools cover all three — a level-order BFS that walks the tree row by row, and a post-order DFS that lets each node decide based on what its two children reported back.

The pattern

A binary tree carries two kinds of information: its layout (how nodes are arranged across levels) and its relationships (how nodes sit relative to one another on root-to-leaf paths). BFS is the natural lens for layout questions because it visits nodes in the exact order a "complete" tree would fill them. DFS — specifically post-order — is the lens for relationship questions, because a node can only judge itself once both children have answered.

The skill is matching the question to the traversal. "Is every level packed, left to right?" is a BFS gap-detection problem. "How few steps to the closest leaf?" is shortest-path, so BFS again. "Where do these two nodes meet?" is about subtree membership, so DFS.

The problems

• Check Completeness of a Binary Tree — BFS the tree and watch for the first missing child; once you've seen a gap, every node after it must also be a leaf-level gap, or the tree isn't complete.
• Minimum Depth of Binary Tree — the shallowest leaf. BFS finds it the instant it dequeues the first leaf (no need to scan the whole tree); a DFS works too but must be careful that a missing child is not a leaf.
• Lowest Common Ancestor of a Binary Tree — post-order DFS returns whether each subtree contains a target; the node where the two targets surface from different children is the split point and the answer.

Key takeaways

• Match the traversal to the question: BFS for level/layout and shortest-distance facts, post-order DFS for relationships between nodes.
• BFS can stop early — minimum depth is found at the first leaf dequeued, not after a full sweep.
• A "gap" flag turns completeness into a single pass — once a hole appears, no later node may have children.
• Why interviewers like it: these problems reveal whether you reach for the right traversal on instinct rather than forcing one tool onto every shape.

Order: Minimum Depth → Check Completeness → Lowest Common Ancestor.