86. Lowest Common Ancestor of a Binary Tree
Find the deepest node whose subtree contains both target nodes, allowing a node to count as its own ancestor. Return the actual ancestor object.
The targets are identified by object identity, not merely by equal values. The contract states what to return if a target is missing.
Example 1
Input
tree=[3,5,1,6,2,0,8,null,null,7,4]; p=node 5, q=node 4
Output
original node 5
Explanation: A requested node can itself be the ancestor.
Example 2
Input
tree=[1,1,1]; p=left child, q=external new Node(1)
Output
null
Explanation: Equal values do not establish membership.
Example 3
Input
p=q=an existing leaf
Output
that leaf identity
Explanation: Self-ancestor semantics still require presence.
Constraints
0 <= node count per tree <= 105-231 <= node.value <= 231 - 1- Each input is a proper binary tree: no cycles or shared child nodes. Null trees are permitted.
Hints
Hint 1
Can an equal-valued external object count as a target?
Hint 2
Record actual parents while traversing until both identities are found.
Hint 3
Mark p’s upward chain, then return the first marked identity on q’s upward chain.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A target can be its own common ancestor
[3,5,1,6,2,0,8,null,null,7,4]
"T1"
"T8"
"T1"