MediumTreeDepth-First SearchBinary Tree

Lowest Common Ancestor of a Binary Tree

1 approach, code in every language

You are given the root of a binary tree together with two distinct nodes, p and q, that are both guaranteed to appear somewhere in the tree.

The lowest common ancestor (LCA) of p and q is the deepest node in the tree that has both p and q somewhere in its subtree. A node is allowed to be a descendant of itself, so if one of the two nodes sits on the path from the root down to the other, that ancestor node is the answer.

Return the node that is the lowest common ancestor of p and q.

Example 1

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

Output: 3

5 lives in the left subtree of 3 and 1 lives in the right subtree, so the deepest node containing both is the root 3.

Example 2

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

Output: 5

4 is a descendant of 5 (5 -> 2 -> 4). Because a node counts as its own ancestor, the LCA is 5 itself.

Constraints

The number of nodes in the tree is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
Both p and q exist in the tree.

Recursive Post-order Search

Recurse into both subtrees; a node whose left and right searches both succeed is the LCA.

Loading animation…

Intuition

Think about what each recursive call reports back: it returns a non-null node if either p or q (or their LCA) was found in that subtree. If the current node is null it found nothing, and if it equals p or q we can immediately report the current node upward. After searching both children, there are only three cases to reason about. When both the left and right calls come back non-null, p was found on one side and q on the other, which means the current node is exactly the split point and therefore the lowest common ancestor. When only one side returns non-null, both targets live in that side, so we bubble that result up unchanged.

Algorithm walkthrough

1Base case: if the node is null, or it is p, or it is q, return the node itself so the caller learns a target was located here.
2Recurse on the left child and store the result; recurse on the right child and store its result.
3If both the left and right results are non-null, p and q were found in different subtrees, so return the current node as the LCA.
4If exactly one side is non-null, return that side, propagating the found target (or already-found LCA) upward.
5If both sides are null, return null so ancestors know nothing was found in this branch.
6The very first call that satisfies the both-sides-non-null condition is the answer that surfaces at the top.

Implementation

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None 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 if left else right

Time

O(n)

Space

O(h)

Every node is visited once, so time is linear in the node count n. The recursion stack uses O(h) space where h is the tree height, up to O(n) for a degenerate (skewed) tree.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free