Bird
Raised Fist0
Interview Preptree-dfsmediumFacebookAmazonMicrosoftGoogleBloomberg

Lowest Common Ancestor of Binary Tree

Choose your preparation mode4 modes available
▶
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.
📊
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

  1. Step 1: Initialize variables

    inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
  2. 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.
  3. 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.
  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.
  5. Final Answer:

    Option D -> Option D
  6. 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

  1. 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.
  2. 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.
  3. Final Answer:

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

  1. Step 1: Analyze height and binary search

    Height h = O(log n). Binary search on last level does O(log n) steps.
  2. 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).
  3. Final Answer:

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

  1. 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.
  2. Step 2: Identify the bug line.

    Line 9 adds 1 incorrectly, causing diameter to be off by one.
  3. Final Answer:

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

  1. Step 1: Identify prefix_counts usage

    prefix_counts tracks how many times a prefix sum has occurred along the current path.
  2. Step 2: Recognize missing decrement on backtrack

    Failing to decrement prefix_counts[current_sum] when backtracking causes counts to accumulate incorrectly across branches.
  3. Final Answer:

    Option A -> Option A
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard