Lowest Common Ancestor in a Binary Search Tree

Quick Overview

Find the lowest common ancestor of two nodes in a binary search tree, with a precise level-order input format and ancestor-as-target edge semantics.

Lowest Common Ancestor in a Binary Search Tree

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement `lowest_common_ancestor(level_order, p, q)` for a binary search tree with unique integer values. Return the integer value of the deepest node whose subtree contains both target nodes. A node belongs to its own subtree, so either target can be the answer. `level_order` encodes the tree in breadth-first order. Its first value is the root. For each non-null node, consume its next left and right child entries; null entries have no children. Omitted trailing children are null. Examples use `null` for an absent child. The input is a valid BST with 2 through 100,000 nodes. Values are between -1,000,000,000 and 1,000,000,000. The distinct values `p` and `q` both exist. Every left-subtree value is smaller than its ancestor; every right-subtree value is larger. ### Examples ```text lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 8) -> 6 lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 4) -> 2 ``` The second result is a target node because its subtree also contains the other target. Return a value rather than a tree-node object; uniqueness makes the answer unambiguous. Problem reference: [LeetCode 235](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/).

Overview: Find the lowest common ancestor of two nodes in a binary search tree, with a precise level-order input format and ancestor-as-target edge semantics.

|Home/Coding & Algorithms/Amazon
Amazon logo
Amazon
Aug 22, 2026
hardSoftware EngineerTechnical ScreenCoding & Algorithms
0
0

Implement lowest_common_ancestor(level_order, p, q) for a binary search tree with unique integer values. Return the integer value of the deepest node whose subtree contains both target nodes. A node belongs to its own subtree, so either target can be the answer.

level_order encodes the tree in breadth-first order. Its first value is the root. For each non-null node, consume its next left and right child entries; null entries have no children. Omitted trailing children are null. Examples use null for an absent child.

The input is a valid BST with 2 through 100,000 nodes. Values are between -1,000,000,000 and 1,000,000,000. The distinct values p and q both exist. Every left-subtree value is smaller than its ancestor; every right-subtree value is larger.

Examples

lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 8) -> 6
lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 4) -> 2

The second result is a target node because its subtree also contains the other target. Return a value rather than a tree-node object; uniqueness makes the answer unambiguous.

Problem reference: LeetCode 235.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...