Lowest Common Ancestor
Mediumjavapythonccppjavascript
Given a binary tree with distinct node values and two values P and Q that both appear in the tree, find the value of their lowest common ancestor (the deepest node that has both P and Q in its subtree).
Input Format
The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null). The third line contains two integers P and Q.
Output Format
Print the value of the lowest common ancestor.
Example 1
Input
7 3 5 1 6 2 0 8 5 1
Output
3
Explanation: Node 3 is the deepest node that has both 5 and 1 in its subtree.
- 1 <= number of nodes <= 5000
- All node values are distinct.
- P and Q both appear in the tree.
Submit an attempt to unlock the solution. (Sign in first.)
Related Problems
- Check Balanced Binary TreeMedium · java, python, c, cpp, javascriptSolve Problem
- Diameter of Binary TreeMedium · java, python, c, cpp, javascriptSolve Problem
- Zigzag Level Order TraversalMedium · java, python, c, cpp, javascriptSolve Problem