Initialize the parent dictionary with root having no parent, and start the stack with the root node to begin DFS traversal.
💡 This sets up the data structures needed to track parent pointers for all nodes.
Line:parent = {root: None}
stack = [root]
💡 We start with the root known and no parents assigned yet for other nodes.
expand
Pop root from stack and process children
Pop node 3 (root) from stack. Add its left child 5 and right child 1 to parent map and stack.
💡 Assigning parents for children is key to building the parent map for ancestor lookup.
Line:node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
💡 Parent pointers for immediate children of root are now known.
expand
Pop node 1 from stack and process children
Pop node 1 from stack. Add its left child 0 and right child 8 to parent map and stack.
💡 Continuing to build parent pointers for deeper nodes.
Line:node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
💡 Parent pointers for nodes 0 and 8 are now known.
expand
Pop node 8 from stack (leaf node)
Pop node 8 from stack. It has no children, so no new parents are added.
💡 Leaf nodes end branches of the DFS traversal.
Line:node = stack.pop()
💡 Traversal backtracks after reaching leaf nodes.
expand
Pop node 0 from stack (leaf node)
Pop node 0 from stack. It has no children, so no new parents are added.
💡 Leaf nodes end branches of the DFS traversal.
Line:node = stack.pop()
💡 Traversal backtracks after reaching leaf nodes.
expand
Pop node 5 from stack and process children
Pop node 5 from stack. Add its left child 6 and right child 2 to parent map and stack.
💡 Continue building parent pointers for nodes deeper in the tree.
Line:node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
💡 Parent pointers for nodes 6 and 2 are now known.
expand
Pop node 2 from stack and process children
Pop node 2 from stack. Add its left child 7 and right child 4 to parent map and stack.
💡 Continue building parent pointers for leaf nodes.
Line:node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
💡 Parent pointers for nodes 7 and 4 are now known.
expand
Pop node 4 from stack (leaf node)
Pop node 4 from stack. It has no children, so no new parents are added.
💡 Leaf nodes end branches of the DFS traversal.
Line:node = stack.pop()
💡 Traversal backtracks after reaching leaf nodes.
expand
Pop node 7 from stack (leaf node)
Pop node 7 from stack. It has no children, so no new parents are added.
💡 Leaf nodes end branches of the DFS traversal.
Line:node = stack.pop()
💡 Traversal backtracks after reaching leaf nodes.
fill_row
Build ancestor set for p (node 5)
Starting from p (node 5), add it and all its ancestors up to root to the ancestor set.
💡 This ancestor set helps quickly check if q's ancestors intersect with p's ancestors.
Line:ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
💡 Ancestor set now contains nodes 5 and 3 (root).
shrink
Move q (node 1) up until found in p's ancestor set
Check if q (node 1) is in p's ancestor set. It is not, so move q up to its parent (node 3).
💡 Moving q up finds the first common ancestor with p.
Line:while q not in ancestors:
q = parent[q]
💡 q's parent is the LCA because it is in p's ancestor set.
return
Return the lowest common ancestor node 3
Node 3 is the lowest common ancestor of nodes 5 and 1, so return it as the answer.
💡 Returning the LCA completes the algorithm.
Line:return q
💡 The LCA is the first node on q's path that is also an ancestor of p.
def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
parent = {root: None} # STEP 1
stack = [root] # STEP 1
while p not in parent or q not in parent: # STEP 2-9
node = stack.pop() # STEP 2-9
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set() # STEP 10
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors: # STEP 11
q = parent[q]
return q # STEP 12
📊
Lowest Common Ancestor of Binary Tree - Watch the Algorithm Execute, Step by Step
Watching this step-by-step reveals how parent pointers simplify ancestor lookup, making the LCA problem easier to understand than recursive approaches.
Step 1/12
·Active fill★Answer cell
Current node: 0
351620874
Current node: 0
351620874
Current node: 2
351620874
Current node: 6
351620874
Current node: 5
351620874
Current node: 1
351620874
Current node: 4
351620874
Current node: 8
351620874
Current node: 7
351620874
Current node: 1
351620874
Current node: 0
351620874
Current node: 0
351620874
Return: 0
Key Takeaways
✓ Parent pointers allow efficient upward traversal to find ancestors without recursion.
This is hard to see from code alone because recursion often hides the explicit parent-child relationships.
✓ Building an ancestor set for one node enables quick membership checks for the other node's ancestors.
Visualizing the ancestor set clarifies why the intersection node is the LCA.
✓ The iterative DFS stack traversal builds the parent map in a controlled order, ensuring all nodes have parents before ancestor tracing.
Seeing the stack operations step-by-step reveals the order nodes are processed and parents assigned.
Practice
(1/5)
1. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?
easy
A. 4
B. 2
C. 1
D. 3
Solution
Step 1: Initialize variables
inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
Step 2: First iteration (i=3, node_val=20)
top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
Step 3: Second iteration (i=2, node_val=7)
top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
Step 4: Third iteration (i=1, node_val=15)
top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
Final Answer:
Option D -> Option D
Quick Check:
inorder_index decremented twice after popping 7 and 20 [OK]
Hint: inorder_index decrements only when popping matching nodes [OK]
Common Mistakes:
Off-by-one error in inorder_index update
Confusing when to pop stack
Misreading top.val vs inorder[inorder_index]
2. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?
medium
A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM
B. Line returning NOT_COVERED at the end of dfs
C. Line checking if dfs(root) == NOT_COVERED after traversal
D. Line returning COVERED_NO_CAM when node is null
Solution
Step 1: Identify camera placement logic
When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.
Step 2: Locate incorrect return
The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.
Final Answer:
Option A -> Option A
Quick Check:
Returning HAS_CAM is essential after placing a camera [OK]
Hint: Return HAS_CAM after placing camera to signal coverage [OK]
Common Mistakes:
Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
Forgetting to add camera if root uncovered
Mixing coverage states in conditions
3. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?
medium
A. O(log n)
B. O(n)
C. O((log n)^2)
D. O(n log n)
Solution
Step 1: Analyze height and binary search
Height h = O(log n). Binary search on last level does O(log n) steps.
Step 2: Combine existence checks
Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).
Final Answer:
Option C -> Option C
Quick Check:
Nested log factors from height and binary search [OK]
Hint: Two nested log factors multiply to (log n)^2 [OK]
Common Mistakes:
Confusing O(log n) with O((log n)^2)
Assuming linear time due to traversal
4. The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.
medium
A. Line 6: if not node: return 0
B. Line 9: diameter = max(diameter, left + right + 1)
C. Line 10: return 1 + max(left, right)
D. Line 2: diameter = 0
Solution
Step 1: Understand diameter definition counts edges, not nodes.
The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.
Step 2: Identify the bug line.
Line 9 adds 1 incorrectly, causing diameter to be off by one.
Final Answer:
Option B -> Option B
Quick Check:
Diameter must be sum of left and right heights (edges), not nodes [OK]
Hint: Diameter counts edges = left + right, not +1 [OK]
Common Mistakes:
Adding 1 to diameter sum
Not using nonlocal for diameter
Returning wrong height value
5. The following code attempts to count the number of paths summing to targetSum using iterative DFS and prefix sums. Which line contains a subtle bug that causes incorrect path counts?
class Solution:
def pathSum(self, root, targetSum):
if not root:
return 0
prefix_counts = {0: 1}
result = 0
stack = [(root, 0, False)] # node, current_sum, visited_children
while stack:
node, current_sum, visited = stack.pop()
if node is None:
continue
if not visited:
current_sum += node.val
result += prefix_counts.get(current_sum - targetSum, 0)
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
stack.append((node, current_sum, True)) # Mark node as visited
stack.append((node.right, current_sum, False))
stack.append((node.left, current_sum, False))
else:
# BUG: Missing decrement of prefix_counts on backtrack
# prefix_counts[current_sum] -= 1
pass
return result
medium
A. Line where prefix_counts[current_sum] should be decremented but is missing
B. Line where prefix_counts[current_sum] is incremented
C. Line where current_sum is incremented by node.val
D. Line where stack appends left and right children
Solution
Step 1: Identify prefix_counts usage
prefix_counts tracks how many times a prefix sum has occurred along the current path.
Step 2: Recognize missing decrement on backtrack
Failing to decrement prefix_counts[current_sum] when backtracking causes counts to accumulate incorrectly across branches.
Final Answer:
Option A -> Option A
Quick Check:
Missing decrement leads to overcounting paths [OK]
Hint: Always decrement prefix_counts on backtrack [OK]
Common Mistakes:
Not decrementing prefix_counts after visiting children
Assuming prefix_counts only grows
Confusing when to mark node as visited
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.