Lowest Common Ancestor of Binary Tree

▶

Steps

setup

Initialize parent map and stack

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.

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. 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

1. Step 1: Identify thread removal step

   Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.

2. Step 2: Locate missing removal

   The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.

3. Final Answer:

   Option A -> Option A

4. 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

2. 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

1. Step 1: Review rewiring steps

   The code sets root.right = prev but does not set root.left = None, so left pointers remain.

2. Step 2: Identify missing step

   Setting root.left = None is required to ensure the flattened list has no left children.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Left pointers must be nullified to meet problem constraints [OK]

Hint: Always set root.left = None when flattening [OK]

Common Mistakes:

• Forgetting to nullify left pointers
• Misordering recursive calls causing wrong sequence
• Losing subtree references by incorrect rewiring

3. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?

medium

A. O(n^2) due to checking grandchildren nodes explicitly

B. O(n) but with extra O(n) space for memoization arrays

C. O(n) because each node is visited once in DFS

D. O(n log n) because of recursive calls and combining results

Solution

1. Step 1: Identify DFS traversal cost

   The algorithm visits each node exactly once in a postorder DFS traversal.

2. Step 2: Analyze operations per node

   At each node, constant time operations are done: combining left and right child results, no repeated work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal of n nodes -> O(n) time [OK]

Hint: DFS visits each node once, no repeated subproblems [OK]

Common Mistakes:

• Assuming O(n^2) due to grandchildren checks
• Confusing recursion stack space with time complexity

4. Suppose the problem is modified so that the tree can have nodes with arbitrary large depth, and you want to avoid recursion stack overflow. Which approach is best to check if the tree is balanced efficiently?

hard

A. Use the brute force recursive height check since it is simpler to implement.

B. Use iterative postorder traversal with a stack to compute heights and check balance.

C. Use a breadth-first traversal and check balance at each level.

D. Use a global variable to store height and recurse with tail recursion optimization.

Solution

1. Step 1: Understand recursion stack limitations

   Deep trees can cause recursion stack overflow in recursive solutions.

2. Step 2: Identify iterative approach benefits

   Iterative postorder traversal uses explicit stack, avoiding recursion limits and still computes heights and balance in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative approach avoids recursion depth issues [OK]

Hint: Iterative traversal avoids recursion stack overflow [OK]

Common Mistakes:

• Assuming recursion with tail call optimization works in Python
• Using BFS which does not check subtree height balance
• Choosing brute force recursion despite stack limits

5. Suppose the problem is modified so that node values can be negative, and you want to find all root-to-leaf paths summing to targetSum. Which modification to the DFS approach is necessary to ensure correctness?

hard

A. Remove pruning and explore all paths fully since negative values can reduce sums

B. Add pruning to stop exploring paths when current_sum exceeds targetSum

C. Use BFS instead of DFS to avoid infinite loops caused by negative values

D. Sort children nodes by value to explore promising paths first

Solution

1. Step 1: Understand effect of negative values

   Negative values can decrease current_sum, so pruning based on exceeding targetSum can miss valid paths.

2. Step 2: Adjust DFS to remove pruning

   To ensure all valid paths are found, pruning must be removed and all paths fully explored.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pruning breaks correctness with negative values; full exploration needed [OK]

Hint: Negative values invalidate pruning based on sum limits [OK]

Common Mistakes:

• Applying pruning blindly
• Switching to BFS unnecessarily