How to Find Lowest Common Ancestor in a Tree

To find the lowest common ancestor (LCA) of two nodes in a tree, start from the root and recursively check if the nodes lie in the left or right subtree. The LCA is the node where the paths to the two nodes split or the node itself if it matches one of the targets.

Syntax

The typical function to find the LCA takes three inputs: the root of the tree, and the two nodes p and q whose LCA you want to find. It returns the node that is the lowest common ancestor.

• root: The current node in the tree during recursion.
• p and q: The two nodes to find the LCA for.
• Returns: The node that is the LCA of p and q.

python

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)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Example

This example demonstrates finding the LCA in a simple binary tree. It builds the tree, selects two nodes, and prints their lowest common ancestor.

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)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

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

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, node5, node1)
print(f"LCA of 5 and 1 is: {lca.val}")

lca2 = lowest_common_ancestor(root, node7, node4)
print(f"LCA of 7 and 4 is: {lca2.val}")

Output

LCA of 5 and 1 is: 3
LCA of 7 and 4 is: 2

Common Pitfalls

Common mistakes when finding the LCA include:

• Not handling the case when one node is the ancestor of the other.
• Assuming the tree is a binary search tree and using value comparisons instead of structure.
• Not checking for None nodes during recursion, which can cause errors.

Always ensure your function works for general binary trees, not just binary search trees.

python

def wrong_lca(root, p, q):
    # Incorrect: assumes BST and compares values
    if root is None:
        return None
    if root.val > p.val and root.val > q.val:
        return wrong_lca(root.left, p, q)
    if root.val < p.val and root.val < q.val:
        return wrong_lca(root.right, p, q)
    return root

# Correct approach does not rely on values but on subtree presence

Quick Reference

• Check if current node is None or matches p or q.
• Recursively search left and right subtrees.
• If both sides return non-None, current node is LCA.
• If only one side returns a node, propagate it up.

Key Takeaways

The lowest common ancestor is the deepest node that has both target nodes as descendants.

Use recursion to explore left and right subtrees and find where paths to nodes diverge.

Do not assume the tree is a binary search tree unless specified; rely on structure, not values.

Handle cases where one node is ancestor of the other by returning the matching node immediately.

Always check for null nodes to avoid errors during recursion.