Is the tree filled without gaps
Check whether a binary tree is complete - every level full except possibly the last, which fills from the left - using a row-by-row walk that notices the first gap. About 14 minutes.
Real nodes first, then only holes
A complete tree fills each level fully, except maybe the last, which fills from the left. If you list the slots in level order, counting empty places too, you see real nodes first and then only empty places. A real node after an empty place means a gap.
So walk in level order, but also queue the missing children, as empty entries. Keep a flag that says whether an empty entry has been seen.
node = q.popleft()
if node is None:
gap = True- gap
- no
Take 1. Queue its children 2 and 3. No gap yet.
A real node after a gap
When you take a real node from the queue, check the flag. If a gap was seen before, the tree is not complete: return false at once. Otherwise queue both of its children, left then right, even if they are missing.
If the whole walk ends without finding a real node after a gap, the tree is complete. An empty tree counts as complete.
else:
if gap:
return False
q.append(node.left)
q.append(node.right)A tree is read in level order and the slots go: node, node, none, node. Is it complete?
- ANo, because a real node follows an empty slot
- BYes, since most slots are filled
- CIt depends on how many levels there are
Show the answer
No, because a real node follows an empty slot. In a complete tree all real nodes come before the first empty slot.
Check completeness of a binary tree
Given the root of a binary tree, return true if it is a complete binary tree: every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible. An empty tree is complete.
root = [1, 2, 3, 4, 5, null, 7] → false
0 ≤ number of nodes ≤ 1,000 · 1 ≤ node.val ≤ 1,000