505. Shared Ancestor in Order
A company stores its employees in a binary search tree keyed by employee number: keys in a node's left subtree are smaller, keys in its right subtree are larger, and all numbers are distinct. Two employees p and q, both nodes of the tree root, need a common point of escalation.
Return the lowest common ancestor of p and q: the deepest node that has both of them in its subtree, where a node counts as being in its own subtree. So if p is above q, the answer is p, and if p and q are the same node, the answer is that node.
Example 1
- Input:
- root = [50,30,70,20,40,60,80]p = {"nodeOf":0,"val":20}q = {"nodeOf":0,"val":40}
- Output:
- 1
- Explanation:
The nodes 20 and 40 are on opposite sides of 30, and 30 is the deepest node that has both below it.
Example 2
- Input:
- root = [50,30,70,20,40,60,80]p = {"nodeOf":0,"val":30}q = {"nodeOf":0,"val":80}
- Output:
- 0
- Explanation:
30 lies in the left subtree and 80 in the right subtree of the root, so the root 50 is the answer.
Constraints
1 ≤ number of nodes ≤ 104
-109 ≤ Node.val ≤ 109
The tree is a valid binary search tree with distinct keys, and both p and q are nodes of the tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(1)