BST Lowest Common Ancestor

Problem

Find the lowest common ancestor of two values in a binary search tree.

Insert values in order (duplicates ignored). Starting at the root, descend left while both values are smaller and right while both are larger; the first node that is not on the same side is the LCA. If either value is missing return None.

Return the value of the LCA.

Hint

In a BST the split point where the two search paths diverge is the lowest common ancestor.

Test cases

case 1

in: [[6,2,8,0,4,7,9,3,5],2,8]

expected: 6

case 2

in: [[6,2,8,0,4,7,9,3,5],2,4]

expected: 2

case 3

in: [[6,2,8,0,4,7,9,3,5],3,5]

expected: 4

case 4

in: [[5],5,5]

expected: 5

case 5

in: [[3,1],4,1]

expected: null

Starter codePython

def bst_lca(values, p, q):
    # Your code here
    pass

5 test cases · run your code against them in the editor