Lowest Common Ancestor in a Binary Search Tree

Find the lowest common ancestor of two node values in a BST using its ordering property.

bst lca tree recursion

Given the root of a binary search tree (BST) and two node values `p` and `q` that exist in the tree, return the value of their lowest common ancestor (LCA). The LCA of two node values is the value of the lowest node that has both values as descendants (a node can be a descendant of itself). Use the BST property: for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. Implement the function `lca_bst(root, p, q)` that returns the integer value of the LCA.

**Tree representation:** The tree is built from nested dictionary objects for testing purposes. Each node is a dictionary with keys `"val"` (integer), `"left"` (node or None), and `"right"` (node or None). The parameter `root` is the root node dictionary. The parameters `p` and `q` are integers representing node values. The tree is a valid BST and `p` and `q` are guaranteed to be present. If `p == q`, the LCA is that node itself.

Constraints

1 <= number of nodes <= 10^4
Node values are unique integers.
`p` and `q` are guaranteed to exist in the tree.
Expected time complexity: O(h) where h is the height (worst-case O(n)), space O(h) for recursion or O(1) iterative.

Example

>>> root = {"val": 6, "left": {"val": 2, "left": {"val": 0, "left": None, "right": None}, "right": {"val": 4, "left": {"val": 3, "left": None, "right": None}, "right": {"val": 5, "left": None, "right": None}}}, "right": {"val": 8, "left": {"val": 7, "left": None, "right": None}, "right": {"val": 9, "left": None, "right": None}}}
>>> lca_bst(root, 2, 8)
6
>>> lca_bst(root, 2, 4)
2
>>> lca_bst(root, 7, 9)
8

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Compare the target values to the current node's value: if both are smaller, go left; if both are larger, go right.

If the current node's value lies between p and q (inclusive), it is the LCA.

You can solve iteratively to avoid recursion overhead.

Remember that a node can be an ancestor of itself when p == q or when one is the ancestor of the other.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.