Lowest Common Ancestor of Binary Tree

📋

Problem

Imagine a family tree where you want to find the closest common ancestor of two relatives. This problem models that scenario in a binary tree structure.

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Input: root of the binary tree, and two nodes p and q. Output: the node representing their lowest common ancestor.

The number of nodes in the tree is in the range [1, 10^5].All node values are unique.p and q are different and both exist in the tree.

Edge cases: p is the root and q is a leaf → output is rootp and q are the same node → output is that nodep and q are on different subtrees → output is their common ancestor

</>

IDE

def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)function lowestCommonAncestor(root, p, q)

def lowestCommonAncestor(root, p, q):
    # Write your solution here
    pass

class Solution {
    public int lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Write your solution here
    return 0;
}

function lowestCommonAncestor(root, p, q) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: p or q node value instead of LCAReturning p or q immediately without checking if the other node is in subtree.✅ Return current node only if both left and right recursive calls are non-null or current node matches p or q.

Wrong: Root node value when p and q are in same subtreeAlways returning root or first ancestor found without checking if lower ancestor exists.✅ Use postorder DFS and return current node only if both children contain p and q.

Wrong: Null or incorrect node when p == qNot handling the case when p and q are the same node.✅ Add a check to return p immediately if p == q.

Wrong: TLE or timeout on large inputUsing repeated path searches or inefficient data structures causing O(n^2) complexity.✅ Use a single postorder DFS traversal to find LCA in O(n) time.

✓

Test Cases

Focus on handling minimal and boundary cases like single node trees and identical nodes.

Think about common algorithmic pitfalls like greedy approaches and partial subtree checks.

Optimize your solution to run in linear time with a single DFS traversal.

t1_01basic

Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":1}

Expected3

⏱ Performance - must finish in 2000ms

The LCA of nodes 5 and 1 is 3 because 3 is the lowest node that has both 5 and 1 as descendants.

💡 Think about traversing the tree to find nodes p and q.

💡 Use postorder DFS to check if p or q exist in left or right subtree.

💡 Return current node if both sides contain p and q or if current node is p or q.

Why it failed: Incorrect output means the DFS postorder logic is flawed; ensure you return current node when both children contain p and q or current node matches p or q. This is the canonical basic case.

✓ Correctly identifies the LCA using postorder DFS.

t1_02basic

Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":4}

Expected5

⏱ Performance - must finish in 2000ms

The LCA of nodes 5 and 4 is 5 because 5 is an ancestor of 4 and itself.

💡 Remember a node can be a descendant of itself.

💡 Check if current node matches p or q before checking children.

💡 Return current node if it matches p or q, or if both children contain p and q.

Why it failed: If output is not 5, likely missing the condition that a node can be ancestor of itself; fix by returning current node if it matches p or q immediately.

✓ Correctly handles ancestor-descendant relationship.

t2_01edge

Input{"root":[1],"p":1,"q":1}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree where p and q are the same node; LCA is that node.

💡 Consider the smallest tree possible.

💡 Check if p and q are the same node.

💡 Return p (or q) immediately if they are identical.

Why it failed: Failing this means code does not handle p == q case; fix by adding a check to return p if p == q.

✓ Handles single-node tree and identical p and q correctly.

t2_02edge

Input{"root":[1,2],"p":1,"q":2}

Expected1

⏱ Performance - must finish in 2000ms

p is root and q is leaf; LCA is root node 1.

💡 Test when one node is root and the other is a leaf.

💡 Check if current node matches p or q before recursion.

💡 Return current node if it matches p or q.

Why it failed: If output is not root, code likely misses returning current node when it matches p or q; fix by adding that condition.

✓ Correctly returns root when p is root and q is leaf.

t2_03edge

Input{"root":[1,2,3],"p":2,"q":3}

Expected1

⏱ Performance - must finish in 2000ms

p and q are on different subtrees; LCA is root node 1.

💡 Check both left and right subtrees for p and q.

💡 Return current node if both sides return non-null.

💡 Use postorder traversal to combine results.

Why it failed: If output is not 1, code likely does not return current node when both children contain p and q; fix by returning current node in that case.

✓ Correctly identifies LCA when p and q are in different subtrees.

t3_01corner

Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":7,"q":4}

Expected2

⏱ Performance - must finish in 2000ms

p and q are both descendants of node 2; LCA is 2. Tests correct subtree aggregation.

💡 Check that recursion returns correct node from subtrees.

💡 Ensure you do not stop at first found node but combine results.

💡 Return current node if both left and right recursive calls are non-null.

Why it failed: If output is not 2, code likely returns first found node without checking both subtrees; fix by returning current node when both sides are non-null.

✓ Correctly aggregates results from both subtrees.

t3_02corner

Input{"root":[1,2,null,3,null,4,null,5],"p":5,"q":4}

Expected4

⏱ Performance - must finish in 2000ms

Deep unbalanced tree tests correct ancestor detection in skewed trees.

💡 Test on skewed tree structures.

💡 Check that recursion correctly bubbles up found nodes.

💡 Return current node if it matches p or q or both children return non-null.

Why it failed: If output is not 4, code likely confuses 0/1 or unbounded recursion or misses returning current node when it matches p or q; fix by proper postorder checks.

✓ Handles skewed trees and returns correct LCA.

t3_03corner

Input{"root":[1,2,3,4,5,6,7],"p":4,"q":6}

Expected1

⏱ Performance - must finish in 2000ms

Greedy trap test: naive approach picking first common ancestor fails; correct approach uses postorder DFS.

💡 Beware of greedy approaches that pick first common ancestor found.

💡 Use postorder traversal to ensure lowest common ancestor.

💡 Return current node only if both left and right subtrees contain p and q.

Why it failed: If output is not 1, code likely uses greedy approach returning first ancestor found; fix by using postorder DFS and checking both children.

✓ Correctly avoids greedy trap and finds lowest common ancestor.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"p":99,"q":100}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced binary tree with 100 nodes; algorithm must run in O(n) time within 2 seconds.

💡 Use a single DFS traversal to find LCA.

💡 Avoid repeated traversals or path storage.

💡 Use postorder recursion with early returns.

Why it failed: TLE indicates algorithm is not O(n); likely uses repeated path searches or inefficient data structures; fix by using single postorder DFS traversal.

✓ Algorithm runs in O(n) time confirming efficient DFS approach.

Practice

1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 2, 1]

D. [3, 1, 2]

Solution

1. Step 1: Trace traversal on given tree

   Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.

2. Step 2: Process nodes in postorder

   3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches postorder [3, 2, 1] [OK]

Hint: Postorder output for this tree is [3,2,1] [OK]

Common Mistakes:

• Confusing order of appending nodes
• Off-by-one in stack popping

2. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

3. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?

medium

A. Line creating root node with postorder[-1]

B. Line initializing inorder_index to 0

C. Line attaching node as right child

D. Line popping from stack inside while loop

Solution

1. Step 1: Identify inorder_index initialization

   inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.

2. Step 2: Consequences of wrong initialization

   Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct inorder_index initialization is critical for stack popping logic [OK]

Hint: inorder_index must start at last index, not zero [OK]

Common Mistakes:

• Wrong inorder_index initialization
• Confusing postorder traversal direction
• Incorrect stack popping conditions

4. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

5. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Solution

1. Step 1: Understand when sums should be added

   Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.

2. Step 2: Identify incorrect addition

   Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum only at leaves fixes the bug [OK]

Hint: Add to total only at leaf nodes [OK]

Common Mistakes:

• Adding partial path sums at non-leaf nodes
• Not resetting total between calls