Find LCA in a BST | Amazon Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find LCA in a BST states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Find LCA in a BST

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given the root of a binary search tree and two keys p and q, return the value of their lowest common ancestor (the deepest node whose value lies between p and q inclusive). Provide both iterative and recursive solutions, and handle the case when one or both keys may be absent by returning a sentinel or raising an error.

Overview: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find LCA in a BST states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a binary search tree (BST) and two keys `p` and `q`, return the value of their lowest common ancestor (LCA) — the deepest node whose value lies between `p` and `q` inclusive. To keep the input language-agnostic, the tree is given as `insert_order`: a list of integers inserted into an initially empty BST using standard BST insertion (left if smaller, right if larger, duplicates ignored). Reconstruct the BST from this list, then find the LCA of `p` and `q`. Handle the case where one or both keys are absent: if either `p` or `q` does not exist in the BST, return the sentinel value `-1`. (All test trees use non-negative values, so `-1` is an unambiguous "not found" signal.) If the tree is empty, also return `-1`. The canonical BST LCA walk: starting at the root, if both keys are smaller than the current node go left, if both are larger go right, otherwise the current node is the LCA. This is the iterative solution. The equivalent recursive form is: ``` def lca(node, p, q): if node.val > p and node.val > q: return lca(node.left, p, q) if node.val < p and node.val < q: return lca(node.right, p, q) return node.val ``` **Example:** `insert_order = [6, 2, 8, 0, 4, 7, 9, 3, 5]`, `p = 2`, `q = 8` → `6` (the root is the split point between the two subtrees). With `p = 2`, `q = 4` → `2` (since 2 is an ancestor of 4). With `p = 3`, `q = 5` → `4`.

Constraints

0 <= len(insert_order) <= 10^4
0 <= node values <= 10^9 (all non-negative so -1 is an unambiguous 'not found' sentinel)
All values in insert_order are distinct (duplicates are ignored on insertion)
p and q are integers; they may or may not be present in the BST

Examples

Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 2, 8)

Expected Output: 6

Explanation: 2 lives in the left subtree and 8 in the right subtree of the root, so the root 6 is the split point and the LCA.

Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 2, 4)

Expected Output: 2

Explanation: 4 is a descendant of 2, so the deeper ancestor common to both is 2 itself.

Hints

Reconstruct the BST first: walk down from the root for each value, going left when smaller and right when larger, attaching a new node where you fall off the tree.
Use the BST property for the LCA: the lowest common ancestor is the first node (from the root) whose value lies between p and q inclusive. If the node is greater than both keys go left; if less than both go right; otherwise it is the answer.
Before searching, verify both p and q actually exist in the tree with two ordinary BST lookups — return -1 if either lookup fails or the tree is empty.