Lowest Common Ancestor in a Binary Tree

Lowest Common Ancestor in a Binary Tree

January 6, 2024
medium
DFS, Binary Tree

Problem #

Given a binary tree (not a binary search tree) and two nodes values, find the lowest common ancestor (LCA) of the two 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 (where we allow a node to be a descendant of itself).

Example # 

Input: Root of the Binary Tree, p = 5, q = 1
       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Solution Approach #

Algorithm: Recursive Depth-First Search

The idea is to traverse the tree starting from the root. If either p or q matches the current node, we report it back to its parent. The parent will then report itself to its parent if it receives reports from both children, indicating that it is the LCA.

Algorithm Steps #

  1. Start from the Root: Begin the traversal from the root node.
  2. Check Current Node:
    • If the current node is either p or q, return the current node to its parent.
  3. DFS on Left and Right Child:
    • Recursively perform the search on the left and right children.
  4. Identify LCA:
    • If both left and right recursion return non-null values, the current node is the LCA.
    • If only one of the children returns a non-null value, return that value upwards.

Python Code # 

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

def lowestCommonAncestor(root, p, q):
    if root is None 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

# Example Usage
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 with value 5
q = root.right  # Node with value 1
print(lowestCommonAncestor(root, p, q).val)
# Output: 3

Time Complexity #

  • O(N): The algorithm traverses each node once, where N is the number of nodes in the binary tree.

Space Complexity #

  • O(N): The space complexity is mainly due to the recursion stack, which in the worst case can go up to the height of the tree (N).