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.
Examples
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.
Constraints
- 0 = Number of nodes = 105
- -10? = Node.data = 10?
Companies
Topics
Solution.cs C#JavaPythonC++Javascript
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions