Lowest Common Ancestor in BST

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Lowest Common Ancestor in BST. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output