Lowest Common Ancestor of a BST
You are given the root of a binary search tree (every value in a node's left subtree is smaller than the node, every value in its right subtree is larger, and all values are distinct) and two different values p and q that both exist in the tree.
Return the value of their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if p is an ancestor of q, the answer is p.
Use the BST ordering; you do not need to search the whole tree. Return a number (the node's val), not a node.
Constraints
- The tree has between
2and10^5nodes. -10^9 <= Node.val <= 10^9, all values distinct.p !== q, and both values exist in the tree.
Examples
Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6
2 is in the left subtree of 6 and 8 is in the right subtree, so the paths split at the root, 6.
Example 2
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2
4 is below 2, and a node counts as its own ancestor, so the answer is 2.
Example 3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 5 Output: 4
Both are descendants of 4 (3 on its left, 5 on its right).
JavaScript you'll use: Recursion, the call stack and memoization Linked list and tree nodes
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode} root
* @param {number} p
* @param {number} q
* @return {number}
*/
function lowestCommonAncestorBST(root, p, q) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.