Check Completeness of Binary Tree
Mahabharata — The Complete Formation — Every Level Filled Except the Last, All Left-Aligned
पूर्ण वृक्ष — अंतिम स्तर को छोड़ बाकी भरा। Null देखने के बाद — कोई नोड नहीं होना चाहिए॥
*Complete tree — all levels full except last. After seeing null — no more nodes should appear.*
The Story
A complete binary tree has all levels fully filled except possibly the last, which must have all nodes as far left as possible. Check if a given tree is complete.
For `[1,2,3,4,5,6]`: true (complete). For `[1,2,3,4,5,null,7]`: false (7 is right child of 3 but position 6 is null).
**BFS with null-sentinel:** - Do BFS, enqueuing both children (even if null) - Once we see the first null: set `seenNull = true` - If we see any non-null after `seenNull`: not complete!
```java public boolean isCompleteTree(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); q.offer(root); boolean seenNull = false; while (!q.isEmpty()) { TreeNode node = q.poll(); if (node == null) { seenNull = true; } else { if (seenNull) return false; // Non-null after null → not complete! q.offer(node.left); q.offer(node.right); } } return true; } ```
Trace `[1,2,3,4,5,null,7]`: - BFS: 1→poll 1, enqueue 2,3. seenNull=false - poll 2, enqueue 4,5. poll 3, enqueue null,7 - poll 4, enqueue null,null. poll 5, enqueue null,null. - poll null → seenNull=true - poll null, poll null (from 4,5 children)... - poll 7: seenNull=true and 7 is non-null → return false ✓
The Node Count Approach
Count total nodes n. In a complete tree, node at BFS position i must be present for i ≤ n. Check each node's position.
// Position-based check:
int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
boolean isComplete(TreeNode root, int idx, int n) {
if (root == null) return true;
if (idx >= n) return false; // Node exists at position >= n
return isComplete(root.left, 2*idx+1, n) && isComplete(root.right, 2*idx+2, n);
}The BFS SeenNull Sentinel Wisdom
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean seenNull = false;
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
seenNull = true;
} else {
if (seenNull) return false;
q.offer(node.left);
q.offer(node.right);
}
}
return true;
}Step-by-Step Walkthrough
Single node [1]: BFS: poll 1, enqueue null,null. Poll null→seenNull. Poll null→seenNull but already true, no non-null after. Return true ✅
Deep Insight
**Why enqueue nulls?** By adding null to the queue for missing children, we simulate the 'ideal' BFS order of a complete binary tree. In a truly complete tree, all nulls come at the end. Any non-null appearing after a null signals a gap — violating completeness.
**Complete vs Full vs Perfect:** - Complete: all levels full except last; last level left-aligned - Full: every node has 0 or 2 children - Perfect: all levels completely filled
**Index-based check (alternative):** For n nodes, node positions 0..n-1 in BFS order. Any node at index i should have children at 2i+1 and 2i+2 (if < n). Elegant but requires counting nodes first.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Count nodes + index-based DFS |
| Optimal | O(n) | O(n) | BFS with null children; queue holds at most one level |
Pattern Recognition
✅ Complete tree: BFS with null children enqueued ✅ seenNull flag: once set, any non-null → false ✅ O(n) single BFS pass ✅ Alternative: node count + index position check **LeetCode Trigger Phrases:** → "check completeness of binary tree" → All nodes left-aligned in last level → BFS with null-sentinel pattern
Isha Upanishad (cited in Gita tradition)
पूर्णमदः पूर्णमिदं पूर्णात्पूर्णमुदच्यते। पूर्णस्य पूर्णमादाय पूर्णमेवावशिष्यते॥
That is whole; this is whole. From the whole, the whole becomes manifest. Taking the whole from the whole, the whole remains.
Connection: A complete binary tree is whole at every level except the last — all positions filled, no gaps in the internal levels. The BFS check verifies this wholeness: in a truly complete tree, no non-null node should appear after a null gap. Like the Upanishadic teaching that completeness is self-consistent and self-sustaining, a complete binary tree maintains its structural integrity — every level above the last is perfectly filled.