Find the lowest node in a binary tree that is an ancestor of two given nodes.
Lowest Common Ancestor of a Binary Tree
Given the root of a binary tree and two distinct nodes p and q, return their lowest common ancestor (LCA).
A node x is a common ancestor of p and q if both nodes are in the subtree rooted at x (a node is also considered its own ancestor). The lowest common ancestor is the common ancestor that is farthest from the root.
You may assume both target nodes exist in the tree.
Your task is to determine the LCA node and return a reference to it.
Input Format
- The first input is the root of a binary tree.
- Two target nodes
pandqare provided as node references/values depending on the platform representation. - The tree contains no duplicate node identities for the targets.
Output Format
- Return the node that is the lowest common ancestor of
pandq.
Constraints
- The tree is a binary tree.
pandqare present in the tree.pandqare distinct.- A node may be the ancestor of itself.
- Aim for better than brute-force repeated ancestor scanning when possible.
Example 1
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
Explanation
Node 3 is the first node whose subtree contains both 5 and 1, so it is their lowest common ancestor.
Example 2
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
Explanation
Node 5 is an ancestor of node 4, and also of itself, so it is the lowest common ancestor.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.