Lowest Common Ancestor of a Binary Tree

Medium Problem 76 of 151 Java and Python

Problem

Given a binary tree (not necessarily a BST) and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both as descendants. A node is a descendant of itself.

Example 1

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

Example 2

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Why: 4 is below 5, so 5 is the LCA.

Constraints

2 ≤ number of nodes ≤ 10⁵
All values are unique; p and q exist and are different.

Explanation

Ask each subtree: "did you find p or q?" If the left subtree finds one and the right subtree finds the other, the current node is where their paths meet.

If a node is p or q, return it immediately: either the other one is below it (so it is the LCA) or elsewhere (and a higher node will combine them).

Approach 1 · Naive

Compare root-to-node paths

Time O(n)
Space O(h) for the paths, more passes

Record the path from the root to p and to q, then return the last node the two paths share.

Find each path with a DFS that backtracks.
Walk both paths together; the last common node is the LCA.

Java

import java.util.*;

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        TreeNode lca = null;
        for (int i = 0; i < Math.min(pathP.size(), pathQ.size()) && pathP.get(i) == pathQ.get(i); i++) {
            lca = pathP.get(i);
        }
        return lca;
    }

    private boolean findPath(TreeNode node, TreeNode target, List<TreeNode> path) {
        if (node == null) {
            return false;
        }
        path.add(node);
        if (node == target || findPath(node.left, target, path) || findPath(node.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

Python

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def find_path(node, target, path):
            if not node:
                return False
            path.append(node)
            if node is target or find_path(node.left, target, path) or find_path(node.right, target, path):
                return True
            path.pop()
            return False

        path_p, path_q = [], []
        find_path(root, p, path_p)
        find_path(root, q, path_q)
        lca = None
        for a, b in zip(path_p, path_q):
            if a is not b:
                break
            lca = a
        return lca

Approach 2 · Optimal

One recursion

Time O(n)
Space O(h)

Return p or q when found; a node whose two subtrees both return something is the LCA.

If the node is null, p or q, return it.
Recurse left and right.
If both results are non-null, return the node; otherwise return whichever is non-null.

Java

class Solution {
    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;
    }
}

Python

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root is p or root is 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

Complexity compared

Approach	Time	Space
Naive Compare root-to-node paths	O(n)	O(h) for the paths, more passes
Optimal One recursion	O(n)	O(h)

Key takeaways

This is one of the most asked tree questions; be able to explain why returning early at p is safe.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem