Lowest Common Ancestor in Binary Tree in DSA Python

Mental Model

Find the closest shared parent node of two given nodes in a tree by exploring paths from the root.

Analogy: Imagine a family tree where you want to find the closest common grandparent of two cousins by tracing their parents upwards until they meet.

       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4

Here, 3 is root, 5 and 1 are children, and so on.

Dry Run Walkthrough

Input: Binary tree as above, find LCA of nodes 7 and 4

Goal: Find the lowest node that is an ancestor of both 7 and 4

Step 1: Start at root node 3, check left subtree for nodes 7 and 4

3 -> left subtree (5) -> right subtree (1)
Looking for 7 and 4

Why: We begin from root to find where both nodes appear

Step 2: At node 5, check left child 6 (no 7 or 4), then right child 2

5 -> left child 6 (no match)
5 -> right child 2 -> children 7 and 4

Why: We explore left subtree to find nodes

Step 3: At node 2, find node 7 in left child and node 4 in right child

2 -> left child 7 (found)
2 -> right child 4 (found)

Why: Both nodes found under 2, so 2 is common ancestor

Step 4: Return node 2 up to node 5, check right subtree 1 (no 7 or 4)

Left subtree returns 2
Right subtree returns null

Why: Only left subtree contains both nodes

Step 5: Since left subtree returned 2 and right subtree null, LCA is 2

Lowest common ancestor is node 2

Why: 2 is the lowest node with both nodes as descendants

Result:

2

Annotated Code

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root, p, q):
    if root is None:
        return None
    if root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)  # search left subtree
    right = lowest_common_ancestor(root.right, p, q)  # search right subtree

    if left and right:
        return root  # p and q found in different subtrees, root is LCA
    return left if left else right  # return non-null child or None

# Build tree from dry_run input
node7 = TreeNode(7)
node4 = TreeNode(4)
node2 = TreeNode(2, node7, node4)
node6 = TreeNode(6)
node5 = TreeNode(5, node6, node2)
node0 = TreeNode(0)
node8 = TreeNode(8)
node1 = TreeNode(1, node0, node8)
root = TreeNode(3, node5, node1)

lca = lowest_common_ancestor(root, node7, node4)
print(lca.val if lca else 'None')

if root is None:

stop recursion if reached empty subtree

if root == p or root == q:

found one of the target nodes

left = lowest_common_ancestor(root.left, p, q)

search left subtree for targets

right = lowest_common_ancestor(root.right, p, q)

search right subtree for targets

if left and right:

both targets found in different subtrees, current root is LCA

return left if left else right

return whichever subtree found a target or None

Output

2

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing paths for both nodes and then comparing, this approach uses less space and is simpler

Edge Cases

One or both nodes not present in tree

Function returns None if neither node found or returns the node if only one found

DSA Python

if root == p or root == q:

Tree with only one node which is p and q

Returns that node as LCA immediately

DSA Python

if root == p or root == q:

Nodes are the same node

Returns that node as LCA

DSA Python

if root == p or root == q:

When to Use This Pattern

When asked to find the closest shared ancestor of two nodes in a tree, use the Lowest Common Ancestor pattern by recursively searching subtrees and combining results.

Common Mistakes

Mistake: Returning root immediately without checking both subtrees
Fix: Check both left and right subtrees to ensure both nodes are found before deciding LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return the node immediately if root matches p or q to handle ancestor cases

Summary

Finds the lowest node that is an ancestor of two given nodes in a binary tree.

Use when you need to find a shared parent node closest to two nodes in a tree.

The key insight is to recursively search left and right subtrees and combine results to find the lowest common ancestor.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The root node of the binary tree

B. The node with the smallest value between the two nodes

C. The deepest node that is an ancestor of both nodes

D. The parent node of the first node

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants.

2. Step 2: Compare options with definition

   The deepest node that is an ancestor of both nodes matches the definition exactly. Other options describe different nodes.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option C

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the deepest shared parent node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is always the parent of one node

2. Which of the following is the correct Python function signature to find LCA in a binary tree node class named TreeNode?

easy

A. def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

B. def find_lca(root, p, q): return int

C. def find_lca(root: int, p: int, q: int) -> TreeNode:

D. def find_lca(root: TreeNode, p: TreeNode, q: TreeNode): return str

Solution

1. Step 1: Check parameter types and return type

   The function should accept three TreeNode objects and return a TreeNode object representing the LCA.

2. Step 2: Match with options

   def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: correctly uses type hints for parameters and return type. Others have wrong types or return types.

3. Final Answer:

   def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: -> Option A

4. Quick Check:

   Correct signature uses TreeNode and returns TreeNode [OK]

Hint: Use TreeNode type hints for nodes and return [OK]

Common Mistakes:

• Using int instead of TreeNode for parameters
• Returning wrong type like int or str
• Omitting return type annotation

3. Given the following binary tree and code, what will be the output?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

# Tree:
#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

p = root.left  # Node 5
q = root.left.right.right  # Node 4

ancestor = lowestCommonAncestor(root, p, q)
print(ancestor.val)

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace recursive calls for nodes 5 and 4

   Node 5 is root.left, node 4 is root.left.right.right. The LCA is the lowest node that has both as descendants. Node 5 is an ancestor of node 4.

2. Step 2: Identify the LCA node

   Since 5 is ancestor of 4, LCA is node 5 itself.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   LCA(5,4) = 5 [OK]

Hint: If one node is ancestor of other, LCA is that node [OK]

Common Mistakes:

• Choosing root (3) instead of ancestor node
• Confusing node values with LCA
• Ignoring that node can be ancestor of itself

4. The following code attempts to find the LCA but has a bug. What is the error?

def lowestCommonAncestor(root, p, q):
    if not root:
        return None
    if root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    if left:
        return left
    else:
        return right

# Bug: The function sometimes returns None even if both nodes exist in tree.

medium

A. The function should not return root when left and right are both found

B. The function does not check if both nodes exist in the tree before returning

C. The function should return left and right together instead of root when both exist

D. The base case should return root instead of None when root is None

Solution

1. Step 1: Analyze base cases and recursive returns

   The function returns None if root is None, and returns root if root matches p or q. It then searches left and right subtrees.

2. Step 2: Identify missing check for node existence

   If one node is not in the tree, the function may return None incorrectly. It does not verify both nodes exist before returning LCA.

3. Final Answer:

   The function does not check if both nodes exist in the tree before returning -> Option B

4. Quick Check:

   Missing node existence check causes None returns [OK]

Hint: Verify both nodes exist before returning LCA [OK]

Common Mistakes:

• Assuming both nodes always exist in tree
• Changing base case to return root when root is None
• Returning root incorrectly when both left and right found

5. You have a binary tree where nodes can have duplicate values. How should you modify the LCA function to correctly find the LCA of two nodes p and q given only their values (not references)?

hard

A. Modify the function to find all nodes with given values and find LCA of all pairs

B. Use node references instead of values to avoid ambiguity

C. Modify the function to search nodes by value and return the first matching node found

D. Return the root node always since duplicates confuse the search

Solution

1. Step 1: Understand problem with duplicate values

   When values are duplicated, searching by value alone can find multiple nodes, so LCA must consider all matching nodes.

2. Step 2: Modify approach to handle duplicates

   Find all nodes matching p and q values, then compute LCA for each pair to find the correct lowest common ancestor.

3. Final Answer:

   Modify the function to find all nodes with given values and find LCA of all pairs -> Option A

4. Quick Check:

   Handle duplicates by checking all matching nodes [OK]

Hint: Check all nodes with values to handle duplicates [OK]

Common Mistakes:

• Using only first found node causing wrong LCA
• Assuming node references are always available
• Returning root node incorrectly for duplicates