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.

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/).

Constraints

  • The valid BST has 2 through 100000 non-null nodes with unique values.
  • Every value, including p and q, is between -1000000000 and 1000000000.
  • p and q are distinct values that both exist in the tree.
  • Consume up to two child entries for each non-null node in breadth-first order; null entries have no children, and omitted trailing children are null.
  • Return the ancestor value; a target belongs to its own subtree.

Examples

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

Expected Output: 6

Explanation: The source example splits at the root.

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

Expected Output: 2

Explanation: The second example has one target as the ancestor.

Hints

  1. Null entries do not consume their own child entries.
  2. Either target may itself be the returned ancestor.

Loading coding console...

Show the approach

Approach

Decode the breadth-first stream into parallel arrays of node values and left/right child indices. The arrays append only non-null nodes, so advancing the parent index visits exactly the required queue of parents. For each parent, consume at most two remaining entries and attach each non-null entry to the appropriate side. This preserves the stated queue-based encoding, including interior nulls and omitted final children. Starting at the root, if both targets are smaller than the current value, their common ancestor must lie in its left subtree; if both are larger, it must lie in its right subtree. Otherwise the targets split across this node or one equals it, so this node contains both and no proper descendant can contain both. It is therefore the lowest common ancestor. The targets exist, so each chosen descent has a valid child and terminates. Decoding takes O(L) time for L supplied entries, and traversal takes O(h) for tree height h; the arrays use O(n) space for n nodes. All methods are iterative, including on a skewed tree. The comparisons do not subtract endpoint values, and values fit signed 32-bit integers within the public bounds.

Time complexity:
O(L + h), where L is the level-order input length and h is the tree height.
Space complexity:
O(n) auxiliary space to decode n non-null nodes; O(1) additional traversal space.