Check Completeness of a Binary Tree
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
Given the root of a binary tree, return whether it's complete.
A tree is complete when every level is entirely full, except possibly the last one, and the last level's nodes are packed as far left as possible with no gaps in between them.
Input: root = [64, 32, 96, 16, 48, 80]
Output: True
The first two levels are completely full. The last level has two nodes, 16 and 48, and they sit in the two leftmost open spots.
Input: root = [64, 32, 96, 16, None, 80, 112]
Output: False
32 is missing a right child while its sibling 96 already has both of its children filled in. That's a gap before the tree runs out of nodes.
Input: root = [64, None, 32]
Output: False
64's left slot is empty but its right slot holds 32. A left-first gap like this breaks completeness even though the tree only has two nodes.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.