Lowest Common Ancestor in an Inserted BST
Problem statement
Build a binary search tree by inserting the distinct values of insertionOrder from left to right. For each insertion, values smaller than the current node go left and larger values go right.
Return the value of the lowest common ancestor of the nodes containing p and q. A node may be an ancestor of itself.
Function
bstLowestCommonAncestor(insertionOrder: int[], p: int, q: int) → intExamples
Example 1
insertionOrder = [6,2,8,0,4,7,9,3,5]p = 2q = 8return = 6The two nodes lie on opposite sides of the root, so 6 is their lowest common ancestor.
Example 2
insertionOrder = [6,2,8,0,4,7,9,3,5]p = 2q = 4return = 2The node containing 2 is an ancestor of the node containing 4.
Example 3
insertionOrder = [5]p = 5q = 5return = 5A node is its own lowest common ancestor.
Constraints
1 <= insertionOrder.length <= 100000.- All values in
insertionOrderare distinct integers. pandqboth appear ininsertionOrder.