Skip to main content

Lowest Common Ancestor in General Binary Tree

hard
TreeDepth First SearchBinary TreeDfs Recursive
Asked atAmazonGoogleMicrosoftMetaLinkedinBloomberg

Problem Description

Given the root of a binary tree and two distinct nodes `nodeA` and `nodeB` (guaranteed to exist in the tree), find the **lowest common ancestor (LCA)** of these two nodes.

The LCA is defined as the deepest node that has both `nodeA` and `nodeB` as descendants (a node is considered a descendant of itself).

**Example 1:**
```
10
/ \
6 15
/ \ / \
3 8 12 20
/
7
```
Input: root = [10,6,15,3,8,12,20,null,null,7], nodeA = 6, nodeB = 7
Output: 6
Explanation: Node 7 is a descendant of node 6, so the LCA is node 6 itself.

**Example 2:**
```
(same tree)
```
Input: root = [10,6,15,3,8,12,20,null,null,7], nodeA = 3, nodeB = 20
Output: 10
Explanation: Node 3 is in the left subtree and node 20 is in the right subtree, so the LCA is the root 10.

**Note:** You may assume that node values are unique within the tree, and that both target values are guaranteed to exist.

Constraints

  • The number of nodes is in the range [2, 10^5].
  • Node values are unique integers in the range [-10^5, 10^5].
  • Both nodeA and nodeB are guaranteed to exist in the tree.
  • nodeA != nodeB.

Follow-up

Can you solve this for a forest of trees (multiple roots) where the two nodes may belong to different trees, returning null if they share no common ancestor?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.