Lowest common ancestor in a BST
Mediumtreebinary search tree
The tree is a valid BST with distinct values, and p and q are values in it. Return the value of the lowest node that has both below it (a node counts as its own ancestor).
Examples write a tree level by level, with null for a missing child: [3,9,20,null,null,15,7].
Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6
Example 2
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2
2 is an ancestor of 4, so the answer is 2.
Constraints
- 2 ≤ number of nodes ≤ 10⁵
- p ≠ q, both exist in the tree
Submit checks your solution against 8 tests, including hidden ones.
// Provided by the judge: keep these definitions
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}
/**
* @param {TreeNode|null} root
* @param {int} p
* @param {int} q
* @return {int}
*/
function lowestCommonAncestor(root, p, q) {
}