Start computing the height of the tree by initializing height counter and setting current node to root.
💡 Computing height by going down left children helps determine the number of levels in the tree.
Line:h = 0
while root:
h += 1
root = root.left
💡 Height is the number of levels, which guides the binary search range for last level nodes.
setup
Check if tree is empty or height is 1
Check if root is None or height is 1 to handle trivial cases.
💡 If tree is empty or has only one node, counting is trivial and we can return immediately.
Line:if not root:
return 0
if h == 1:
return 1
💡 Since height is 3, the tree has multiple levels and we need to perform binary search on the last level.
setup
Initialize binary search boundaries for last level
Set left and right pointers to cover all possible node indices on the last level.
💡 The last level can have up to 2^(h-1) nodes indexed from 0 to 2^(h-1)-1.
Line:left, right = 0, 2**(h - 1) - 1
💡 We will binary search in this range to find the last existing node index on the last level.
compare
Binary search iteration 1: Calculate mid index
Calculate mid index as (left + right) // 2 to check if node exists at this index.
💡 Mid index splits the search space to check node existence efficiently.
Line:mid = (left + right) // 2
💡 Mid is 1, so we will check if node at index 1 exists on last level.
traverse
Check existence of node at index 1 on last level
Traverse from root to check if node at index 1 exists on last level by following bits of index.
💡 Node existence is checked by interpreting index bits to decide left or right moves.
Line:exists(mid, h, root)
💡 Node at index 1 exists, so we will move left boundary up.
shrink
Update binary search left boundary after node exists
Since node at mid exists, move left boundary to mid + 1 to search higher indices.
💡 Moving left boundary up narrows search to nodes after mid index.
Line:if exists(mid, h, root):
left = mid + 1
💡 We know nodes up to index 1 exist, so next search is from index 2 to 3.
compare
Binary search iteration 2: Calculate mid index
Calculate new mid index as (left + right) // 2 for next existence check.
💡 Mid index recalculates to narrow down the search space.
Line:mid = (left + right) // 2
💡 Mid is 2, so we check node at index 2 on last level.
traverse
Check existence of node at index 2 on last level
Traverse from root to check if node at index 2 exists on last level by following bits of index.
💡 Checking node existence by interpreting index bits guides traversal left or right.
Line:exists(mid, h, root)
💡 Node at index 2 exists, so we will move left boundary up again.
shrink
Update binary search left boundary after node exists
Since node at mid exists, move left boundary to mid + 1 to search higher indices.
💡 Moving left boundary up narrows search to nodes after mid index.
Line:if exists(mid, h, root):
left = mid + 1
💡 Nodes up to index 2 exist, so next search is index 3 to 3.
compare
Binary search iteration 3: Calculate mid index
Calculate mid index as (left + right) // 2 for last existence check.
💡 Mid index recalculates to check the last possible node index.
Line:mid = (left + right) // 2
💡 Mid is 3, so we check node at index 3 on last level.
traverse
Check existence of node at index 3 on last level
Traverse from root to check if node at index 3 exists on last level by following bits of index.
💡 Checking node existence by interpreting index bits guides traversal left or right.
Line:exists(mid, h, root)
💡 Node at index 3 does not exist, so we will move right boundary down.
shrink
Update binary search right boundary after node does not exist
Since node at mid does not exist, move right boundary to mid - 1 to search lower indices.
💡 Moving right boundary down narrows search to nodes before mid index.
Line:else:
right = mid - 1
💡 Nodes exist up to index 2, so binary search ends with left=3, right=2.
reconstruct
Calculate total nodes count
Calculate total nodes as nodes above last level plus count of nodes found on last level.
💡 Nodes above last level are 2^(h-1)-1, add left boundary as count of last level nodes.
Line:return (2**(h - 1) - 1) + left
💡 Total nodes count is 3 + 3 = 6 for this tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
h = 0 # STEP 1
while root: # STEP 1
h += 1 # STEP 1
root = root.left # STEP 1
return h
def exists(idx, h, root):
left, right = 0, 2**(h - 1) - 1 # STEP 5
for _ in range(h - 1): # STEP 5 loop
mid = (left + right) // 2 # STEP 5
if idx <= mid: # STEP 5 decision
root = root.left # STEP 5
right = mid # STEP 5
else:
root = root.right # STEP 5
left = mid + 1 # STEP 5
return root is not None # STEP 5
def countNodes(root):
if not root: # STEP 2
return 0
h = height(root) # STEP 1
if h == 1: # STEP 2
return 1
left, right = 0, 2**(h - 1) - 1 # STEP 3
while left <= right: # STEP 4 loop
mid = (left + right) // 2 # STEP 4
if exists(mid, h, root): # STEP 5
left = mid + 1 # STEP 6
else:
right = mid - 1 # STEP 12
return (2**(h - 1) - 1) + left # STEP 13
if __name__ == '__main__':
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
print(countNodes(root)) # Output: 6
📊
Count Complete Tree Nodes - Watch the Algorithm Execute, Step by Step
Watching each step reveals how the algorithm efficiently counts nodes without traversing every node, using tree properties and binary search.
Step 1/13
·Active fill★Answer cell
Current node: 1
123456
Current node: 1
123456
123456
123456
Current node: 2
123456
Return: true
123456
123456
Current node: 3
123456
Return: true
123456
123456
Current node: 3
123456
Return: false
123456
123456
Return: 6
Key Takeaways
✓ The algorithm efficiently counts nodes by leveraging the complete tree's height and binary search on the last level.
This insight is hard to see from code alone because it avoids naive traversal and uses tree properties cleverly.
✓ Binary search narrows down the last level nodes by checking existence through bitwise traversal.
Visualizing the traversal path for each index clarifies how the algorithm decides left or right moves.
✓ The final count combines nodes above the last level and the count of existing nodes found on the last level.
Understanding this sum is key to grasping why the algorithm returns the correct total node count.
Practice
(1/5)
1. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below?
Tree structure:
1
/ \
2 3
def preorderTraversal(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
result.append(current.val)
current = current.left
else:
predecessor.right = None
current = current.right
return result
easy
A. [2, 1, 3]
B. [1, 2, 3]
C. [1, 3, 2]
D. [3, 1, 2]
Solution
Step 1: Trace first iteration with current=1
Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.
Step 2: Trace second iteration with current=2
Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).
Step 3: Detect thread at 2.right=1
Since predecessor.right == current, reset 2.right=None, move current=1.right=3.
Step 4: Trace current=3
Node 3 has no left child, append 3, move current=3.right=None, loop ends.
Final Answer:
Option B -> Option B
Quick Check:
Output matches preorder traversal [1,2,3] [OK]
Hint: Morris preorder appends root before left subtree [OK]
Common Mistakes:
Appending nodes in wrong order
Not resetting threaded links
Confusing left and right child traversal
2. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children
Solution
Step 1: Identify handling of empty tree
The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
Step 2: Verify other lines
Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
Final Answer:
Option A -> Option A
Quick Check:
Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
3. What is the time complexity of the optimal greedy postorder traversal solution for the Binary Tree Cameras problem, and why?
medium
A. O(n) because each node is visited once in postorder traversal
B. O(n^2) because each node's state depends on its children's states recursively
C. O(n log n) due to recursive calls and state checks at each node
D. O(h) where h is the height of the tree, since recursion depth equals height
Solution
Step 1: Analyze traversal visits
The algorithm visits each node exactly once in a postorder manner, processing left and right children before the node itself.
Step 2: Consider work per node
Each node's processing is O(1) -- checking children's states and updating counters.
Final Answer:
Option A -> Option A
Quick Check:
Single DFS traversal over n nodes -> O(n) time [OK]
Hint: Each node processed once with constant work [OK]
Common Mistakes:
Assuming recursive calls multiply work to O(n^2)
Confusing recursion depth with total work
Thinking state checks add log n factor
4. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current # create thread
current = current.left
else:
# BUG: missing line to remove thread
result.append(current.val)
current = current.right
return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)
Solution
Step 1: Identify thread removal step
Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
Step 2: Locate missing removal
The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
Final Answer:
Option A -> Option A
Quick Check:
Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
Forgetting to remove thread
Appending node before removing thread
Incorrectly creating thread
5. The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.
medium
A. Missing line to set root.left = None
B. Line: flatten(root.left)
C. Line: root.right = prev
D. Line: flatten(root.right)
Solution
Step 1: Review rewiring steps
The code sets root.right = prev but does not set root.left = None, so left pointers remain.
Step 2: Identify missing step
Setting root.left = None is required to ensure the flattened list has no left children.
Final Answer:
Option A -> Option A
Quick Check:
Left pointers must be nullified to meet problem constraints [OK]
Hint: Always set root.left = None when flattening [OK]