Find the Lowest Common Ancestor in a Binary Search Tree
Company: Microsoft
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
# Lowest Common Ancestor in a Binary Search Tree
## Problem
A binary search tree contains distinct integer values. You are given the tree in level-order form and two values, `p` and `q`, that are present in the tree. In the level-order list, `null` denotes a missing child.
Return the value of the lowest node whose subtree contains both `p` and `q`. A node may be an ancestor of itself.
### Function Contract
Implement `lowestCommonAncestorBST(levelOrder, p, q)`.
- Input: a level-order list containing integers and `null` markers, plus two integer values.
- Output: the integer value of the lowest common ancestor.
### Rules and Edge Cases
- The tree is non-empty and satisfies the binary-search-tree ordering property.
- All node values are distinct.
- Both target values occur in the tree.
- Either target may be the root or an ancestor of the other target.
### Examples
```text
Input: levelOrder = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
```
```text
Input: levelOrder = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
```
```hint Use the ordering invariant
At each node, compare both target values with the node value before choosing a child.
```
```hint Identify the split point
The search can stop when the targets no longer lie strictly on the same side of the current node.
```
Quick Answer: Find the lowest common ancestor of two values in a binary search tree represented in level-order form. Use the BST ordering invariant to locate the first split point while handling root targets and ancestor relationships efficiently.
Implement lowest_common_ancestor_bst(level_order, p, q). The nonempty list is a breadth-first serialization of a binary search tree with null child markers: after the root, each existing node consumes the next left and right child slots. Values are distinct, p and q are present, and a node may be its own ancestor. Return the lowest common ancestor's value.
Constraints
- 1 <= level_order.length <= 15.
- level_order is a valid trimmed breadth-first serialization with null child markers.
- Every non-null value is a distinct integer from -3,000,000,000 through 3,000,000,000.
- The represented tree satisfies the binary-search-tree ordering property.
- p and q are values present in the tree and may be equal.
Examples
Input: ([5], 5, 5)
Expected Output: 5
Explanation: A single target node is its own ancestor.
Input: ([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], 2, 8)
Expected Output: 6
Explanation: The targets split on opposite sides of the root.
Hints
- Use the BST ordering invariant to decide whether both targets lie strictly on one side of the current node.
- Stop at the first node where the target range straddles the node value or includes it.