Lowest Common Ancestor of Binary Tree
You are given the root of a binary tree and two node values p and q. Your task is to find and return the value of their Lowest Common Ancestor (LCA).
The Lowest Common Ancestor of two nodes is:
- The deepest node that has both p and q as descendants.
- A node can be a descendant of itself.
- If one node is an ancestor of the other, then that node is the LCA.
Return the value of the lowest common ancestor.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: Node 3 is the lowest common ancestor of nodes 5 and 1.
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, so it is the lowest common ancestor.
Input: root = [1,2], p = 1, q = 2
Output: 1
Explanation: The root node is the lowest common ancestor.
- 0 = Number of nodes = 105
- -10? = Node.data = 10?
See how the best solutions work
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Keep every attempt
Your submissions, results and runtime history live here. Sign in to start your streak.
1 2 1 2
1
3 5 1 6 2 0 8 null null 7 4 5 1
3