Lowest Common Ancestor in General Binary Tree
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.