Problem
Lowest Common Ancestor of a BST
Medium- trees
- binary-search-tree
Find the lowest common ancestor of two values in the binary search tree root. That is the deepest node whose subtree holds both pVal and qVal. A node's subtree includes the node itself, so one of the two values can be the answer.
The two targets arrive as plain integers, not as node references, and you return the value of the ancestor rather than the node.
Trees in this problem are written as level-order arrays: the root first, then each level from left to right. null marks a missing child, and a missing child has no entries beneath it. Trailing nulls are omitted.
- Input
root = [15, 8, 22, 4, 11, 18, 30], pVal = 4, qVal = 11- Output
8- Explanation
4 is the left child of 8 and 11 is the right child, so 8 is the deepest node with both beneath it.
- Input
root = [15, 8, 22, 4, 11, 18, 30], pVal = 22, qVal = 18- Output
22- Explanation
18 is the left child of 22, so 22 holds both values, counting itself.
Constraints:
- every value in the tree is distinct
pValandqValboth appear in the tree
Follow-up: what changes if the tree has no ordering, so that you can no longer choose a side by comparing values?
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.