Lowest Common Ancestor in BST | Dataford Interview Questions

At Stripe, a service stores hierarchical configuration values in a binary search tree (BST). Given the root of a BST and two node values p and q that are guaranteed to exist in the tree, return the value of their lowest common ancestor (LCA).

The lowest common ancestor of two nodes is the deepest node that has both nodes as descendants, where a node can be a descendant of itself.

Formal Specification

Implement a function that takes:

root: a BST represented as a nested object with keys val, left, and right, or null
p: integer value of the first node
q: integer value of the second node

Return:

The integer value of the lowest common ancestor of p and q

Constraints

2 <= number of nodes <= 10^5
-10^9 <= node.val, p, q <= 10^9
All BST node values are unique
p and q are guaranteed to exist in the tree

Function Signature

def lowest_common_ancestor_bst(root, p, q):

Your question is Lowest Common Ancestor in BST. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem