Lowest Common Ancestor (LCA) in a Binary Tree - Algorithm and Code Examples

Problem Statement❯

Given a binary tree and two nodes (p and q), find their lowest common ancestor (LCA). The LCA of two nodes p and q in a binary tree is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Examples❯

Input Tree	Node 1	Node 2	LCA	Description
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]	5	1	3	LCA is 3 — the lowest node with both 5 and 1 in its subtrees
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]	6	4	5	LCA is 5 — 6 and 4 lie in the left subtree of 5
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]	7	8	3	LCA is 3 — 7 is in left subtree, 8 is in right subtree of root
[1, 2]	1	2	1	LCA is 1 — root node is the ancestor of 2
[1, 2, 3, 4, 5, 6, 7]	4	5	2	LCA is 2 — both nodes are in the left subtree
[1, 2, 3, 4, 5, 6, 7]	4	6	1	LCA is 1 — nodes are in opposite subtrees of root
[1]	1	1	1	LCA is 1 — node is the ancestor of itself
[]	1	2	null	Tree is empty — no LCA can be found

Solution❯

Understanding the Problem

We are given a binary tree and two distinct nodes, p and q. Our task is to find their Lowest Common Ancestor (LCA). The LCA is the deepest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

This problem is important in understanding tree structures and recursive thinking. For beginners, think of LCA as the “fork” in the tree where the paths to p and q split. We’ll solve this step-by-step using a real example and cover all possible cases.

Step-by-Step Solution with Example

Step 1: Analyze the Tree Structure

Let’s consider the following binary tree:

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

Suppose we need to find the LCA of nodes 5 and 1.

Step 2: Understand the Path to Each Node

Path to node 5: 3 → 5

Path to node 1: 3 → 1

The first common node from the root downwards is 3. So, the LCA is 3.

Step 3: Recursive Intuition

We use a recursive function that does the following:

If the current node is null, return null.
If the current node is either p or q, return the current node.
Recursively search left and right subtrees.
If both left and right return non-null, current node is the LCA.
If only one side is non-null, propagate it upwards.

Step 4: Java Code for LCA

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;

    return (left != null) ? left : right;
}

Step 5: Explanation for Beginners

We search down both subtrees. If both subtrees return a match, then the current node is where the paths to p and q diverge — this is the LCA. If only one subtree returns a match, we return that node up the recursive call stack.

Edge Cases

Case 1: Nodes in Different Subtrees

Example: nodes 5 and 1 → LCA is 3. This is the standard scenario.

Case 2: One Node is Ancestor of the Other

Example: nodes 5 and 4 → path is 5 → 2 → 4. Since 5 is an ancestor of 4, LCA is 5.

Case 3: Tree with Only Root and One Child

Example: tree [1,2], nodes 1 and 2 → LCA is 1. Even if the tree is tiny, LCA is still computed correctly.

Case 4: Tree is Empty

Example: tree [] → LCA is null. We should always handle this before running the main logic.

Case 5: p and q Are the Same Node

Example: nodes 2 and 2 → LCA is 2. A node is considered its own ancestor.

Finally

The LCA problem teaches recursive tree traversal and highlights important base conditions. Always understand how the tree is structured, and trace paths for both nodes. Use edge cases during testing to build intuition.

This problem is foundational for solving many other tree-based problems and is a must-know for interviews and practice.

Algorithm Steps❯

If root is null or equal to p or q, return root.
Recursively search for LCA in the left subtree: left = lowestCommonAncestor(root.left, p, q).
Recursively search for LCA in the right subtree: right = lowestCommonAncestor(root.right, p, q).
If both left and right are non-null, then root is the LCA; return root.
If only one of left or right is non-null, return the non-null value.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

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 if left else right

# Example usage:
if __name__ == '__main__':
    # Construct binary 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)

    sol = Solution()
    # Assume we want to find LCA of nodes 7 and 4
    lca = sol.lowestCommonAncestor(root, root.left.right.left, root.left.right.right)
    print('LCA:', lca.val if lca else 'None')

⬅ Previous TopicCheck if All Leaf Nodes are at the Same Level in a Binary Tree

Next Topic ⮕Solve the Tree Isomorphism Problem

Comments

Loading comments...