Katkat
Back

Lowest Common Ancestor in a Binary Search Tree

AmazonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests finding the lowest common ancestor of two values in a Binary Search Tree represented as a level-order serialized list, accounting for self-ancestorship and missing-node edge cases.

Lowest Common Ancestor in a Binary Search Tree

You are given the level-order serialization of a Binary Search Tree (BST) containing unique integer values, along with two query values p and q.

The Lowest Common Ancestor (LCA) between two nodes u and v is defined as the lowest node T in the tree that has both u and v as descendants. Under standard edge semantics, a node can be a descendant of itself (for example, if p is an ancestor of q, the LCA is p).

Your task is to return the value of the LCA of p and q. If either p or q (or both) does not exist in the tree, return None.

Input Format

  • tree: A list representing the standard level-order (breadth-first) traversal of the BST, where None indicates a missing child node. Trailing None values may be omitted.
  • p: An integer representing the first target value.
  • q: An integer representing the second target value.

Function Signature

def lowest_common_ancestor(tree: list[int | None], p: int, q: int) -> int | None:
    pass

Constraints

  • 0 <= len(tree) <= 10^5
  • -10^9 <= tree[i] <= 10^9 for non-null elements.
  • All non-null elements in tree form a valid Binary Search Tree.
  • -10^9 <= p, q <= 10^9
  • p and q may or may not be equal.

Examples

Example 1:

Input: 
tree = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
p = 2
q = 8
Output: 6
Explanation:
The root node with value 6 has 2 in its left subtree and 8 in its right subtree, making 6 the lowest common ancestor.

Example 2:

Input:
tree = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
p = 2
q = 4
Output: 2
Explanation:
Node 2 is an ancestor of node 4. Under self-ancestor semantics, the LCA of 2 and 4 is 2.

Example 3:

Input:
tree = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
p = 2
q = 10
Output: None
Explanation:
Node 10 does not exist in the BST, so no common ancestor exists.

Edge Cases to Consider

  • An empty tree ([]) should return None.
  • p == q: If the node exists in the tree, its LCA with itself is itself. If it does not exist, return None.
  • One or both target values do not exist in the BST.

Hints

Hint 1

First reconstruct the tree structure from the level-order serialization using a queue, or verify node existence during an initial traversal.

Hint 2

Do not assume both nodes exist in the tree; you must verify that both `p` and `q` are present before or during your LCA computation.

Hint 3

For a valid BST, starting at the root: if both `p` and `q` are strictly smaller than the current node, move left; if both are strictly greater, move right; otherwise, the current node is the candidate split point.

Follow-up questions

  • How can you find the LCA directly from the level-order array without fully allocating `TreeNode` objects in memory?
  • If the BST contains duplicate values (e.g., left <= root < right), how would that change your traversal logic?
  • How would you optimize queries if the tree is static and you receive millions of LCA queries for different pairs `(p, q)`?