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

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

Case 1: Normal Case – Nodes are in different subtrees

In this case, both p and q exist in different branches of the tree. For example, if one is in the left subtree and the other in the right subtree, their lowest common ancestor is the first node (from bottom to top) where these two paths merge. Typically, this is a higher-level node like the root.

Example: For nodes 5 and 1 in tree [3,5,1,6,2,0,8,null,null,7,4], the paths are: 5 → 3 and 1 → 3. So, the common ancestor is 3.

Case 2: One Node is Ancestor of the Other

Sometimes one of the nodes (say p) is actually an ancestor of the other node (q). In such cases, the LCA is p itself. This is because a node is considered its own descendant.

Example: For nodes 5 and 4, 5 is an ancestor of 4. So, the LCA is 5.

Case 3: Small Tree or Edge Case

In smaller trees with just a couple of nodes, the root may be the LCA. For example, if you only have a root node and one child, and you're looking for LCA between them, the root will be the answer because both nodes are either the root or under the root.

Example: Tree [1,2], nodes 1 and 2 → LCA is 1.

Case 4: Empty Tree

If the tree is empty (no nodes exist), then it's impossible to find any ancestor, so the result is null. This is a boundary condition and should be checked before starting the algorithm.

Example: Tree [], nodes 1 and 2 → LCA is null.

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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')