Lowest Common Ancestor of a Binary Tree

TreesDFS

25 min

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants.

Example

Example 1:

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

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Solution (Recursive DFS)

The problem can be solved efficiently using a recursive Depth-First Search. The core idea is to traverse the tree and, for each node, determine if it's the LCA.

A node is the LCA if either it is one of the target nodes (p or q), or if one target is in its left subtree and the other is in its right subtree.

Algorithm Steps

Create a recursive function `find(node, p, q)`.
Base Case: If `node` is null, or if `node` is `p` or `q`, return `node`.
Recursively call `find` on the left and right children.
If the left recursive call returns a non-null node and the right call also returns a non-null node, it means `p` and `q` were found in different subtrees. Therefore, the current `node` is the LCA. Return `node`.
If only one of the recursive calls returns a non-null node, it means both `p` and `q` are in that subtree. Propagate that non-null value up the call stack.
If both calls return null, neither `p` nor `q` were found in the subtrees of the current `node`. Return null.

Visiting node 3.

Lowest Common Ancestor Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        
        return left or right