PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

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.

  • Medium
  • Amazon
  • Coding & Algorithms
  • Software Engineer

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.

Quick Answer: 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.

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

Expected Output: 4

Explanation: Both 3 and 5 are children of 4 (3 on the left, 5 on the right), so 4 is the LCA.

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

Expected Output: 2

Explanation: When both keys are the same existing node, that node is its own ancestor and the LCA.

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

Expected Output: 2

Explanation: 0 and 5 both sit under 2 (0 far left, 5 in the 4-subtree), and 2 is the deepest node between them.

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

Expected Output: -1

Explanation: 11 is not present in the BST, so the sentinel -1 is returned.

Input: ([], 1, 2)

Expected Output: -1

Explanation: Empty tree: neither key exists, so return the sentinel -1.

Input: ([5], 5, 5)

Expected Output: 5

Explanation: Single-node tree where both keys equal the root; the root is trivially the LCA.

Input: ([20, 10, 30, 5, 15, 25, 35], 5, 35)

Expected Output: 20

Explanation: 5 is in the far-left subtree and 35 in the far-right subtree, so the root 20 is the LCA.

Hints

  1. 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.
  2. 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.
  3. 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Top-p (Nucleus) Sampling in NumPy - Amazon (medium)
  • Implement Multi-Head Attention from Scratch in NumPy - Amazon (medium)
  • Detect and Break a Cycle in a Singly Linked List - Amazon (medium)
  • Caesar Cipher with Translation-Table Optimization - Amazon (medium)
  • Minimum Drone Delivery Time on a Ring of Hubs - Amazon (medium)