Python Program to Find Lowest Common Ancestor

To find the lowest common ancestor in a binary tree, use a recursive function that returns the node if it matches either target or searches left and right subtrees, returning the current node if both sides find a target; for example, def lca(root, p, q): if not root or root == p or root == q: return root; left = lca(root.left, p, q); right = lca(root.right, p, q); if left and right: return root; return left or right.

Examples

InputTree: [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1

Output3

InputTree: [3,5,1,6,2,0,8,null,null,7,4], p=5, q=4

Output5

InputTree: [1,2], p=1, q=2

Output1

How to Think About It

To find the lowest common ancestor, think of checking if the current node is one of the targets. If yes, return it. Otherwise, search the left and right children. If both sides return a node, it means one target is in each subtree, so the current node is their lowest common ancestor. If only one side returns a node, pass it up.

Algorithm

1

Check if the current node is null or matches one of the target nodes; if yes, return it.

2

Recursively search the left subtree for the targets.

3

Recursively search the right subtree for the targets.

4

If both left and right recursive calls return non-null, current node is the lowest common ancestor; return it.

5

Otherwise, return the non-null result from left or right subtree.

Code

python

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

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

# Example usage:
# Build tree nodes
n3 = TreeNode(3)
n5 = TreeNode(5)
n1 = TreeNode(1)
n6 = TreeNode(6)
n2 = TreeNode(2)
n0 = TreeNode(0)
n8 = TreeNode(8)
n7 = TreeNode(7)
n4 = TreeNode(4)

# Connect nodes
n3.left = n5
n3.right = n1
n5.left = n6
n5.right = n2
n1.left = n0
n1.right = n8
n2.left = n7
n2.right = n4

ancestor = lca(n3, n5, n1)
print(ancestor.val)  # Output: 3

Output

3

Dry Run

Let's trace finding LCA of nodes 5 and 1 in the example tree.

1

Start at root (3)

root=3, p=5, q=1; root is not p or q, so search left and right

2

Search left subtree of 3

root=5 matches p=5, return node 5

3

Search right subtree of 3

root=1 matches q=1, return node 1

4

Both sides returned nodes

left=5, right=1, so return current root 3 as LCA

Call	root.val	left result	right result	Return
lca(3,5,1)	3	5	1	3
lca(5,5,1)	5	None	None	5
lca(1,5,1)	1	None	None	1

Why This Works

Step 1: Base case returns node if it matches

If the current node is null or matches one of the targets, return it immediately to signal a found target.

Step 2: Search left and right subtrees

Recursively look for targets in left and right children to find where targets are located.

Step 3: Determine lowest common ancestor

If both left and right calls return nodes, current node is the lowest common ancestor because targets are in different subtrees.

Alternative Approaches

Path Comparison

python

def find_path(root, target, path):
    if not root:
        return False
    path.append(root)
    if root == target:
        return True
    if (find_path(root.left, target, path) or find_path(root.right, target, path)):
        return True
    path.pop()
    return False

def lca_path_method(root, p, q):
    path_p, path_q = [], []
    if not find_path(root, p, path_p) or not find_path(root, q, path_q):
        return None
    i = 0
    while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:
        i += 1
    return path_p[i-1]

# Usage same as before

This method finds paths to both nodes and compares them; it uses extra space and is less efficient but easier to understand.

Parent Pointers

python

def lca_with_parents(p, q):
    ancestors = set()
    while p:
        ancestors.add(p)
        p = p.parent
    while q:
        if q in ancestors:
            return q
        q = q.parent
    return None

# Requires nodes to have parent pointers set.

This approach uses parent links to find LCA without recursion but needs extra parent references.

Complexity: O(n) time, O(h) space

Time Complexity

The algorithm visits each node once in the worst case, so it runs in O(n) time where n is the number of nodes.

Space Complexity

The recursion stack can go as deep as the tree height h, so space complexity is O(h).

Which Approach is Fastest?

The recursive method is efficient and simple; path comparison uses extra space and time; parent pointer method is fast but requires extra node info.

Approach	Time	Space	Best For
Recursive Search	O(n)	O(h)	General binary trees without parent pointers
Path Comparison	O(n)	O(n)	When understanding paths is easier or tree is small
Parent Pointers	O(h)	O(h)	Trees with parent pointers available