Quick Overview

Given a binary search tree in level-order form and two distinct keys present in it, return the key of their lowest common ancestor, where a node counts as its own ancestor. Tests reasoning with the search tree ordering, plus time and space analysis on skewed trees.

Find the deepest shared ancestor of two keys in a binary search tree

Company: Amazon

Role: Frontend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a binary search tree and two distinct keys `p` and `q` that are both in the tree, return the key of their lowest common ancestor: the node farthest from the root whose subtree contains both `p` and `q`. A node's subtree includes the node itself, so if one of the two keys is an ancestor of the other, that key is the answer. ### Function Signature ```python def lowest_common_ancestor(root: list[int | None], p: int, q: int) -> int: ``` ### Rules - The tree is given in level order. The first element is the root. Then, for each non-null node in the order it appears, the list gives its left child followed by its right child, with `None` for a missing child. Trailing `None` values may be omitted. - All keys are distinct. For every node, every key in its left subtree is smaller than the node's key, and every key in its right subtree is larger. - The common ancestors of `p` and `q` all lie on one path from the root, so exactly one of them is farthest from the root. Return its key. ### Constraints - The tree has between `2` and `100000` nodes. - `-10^9 <= key <= 10^9` for every key - `p != q`, and both `p` and `q` are keys in the tree. - The tree is not necessarily balanced; its height can equal the number of nodes. ### Examples **Example 1** ```text Input: root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 12, q = 5 Output: 10 ``` The root 20 has children 10 and 30. Node 10 has children 5 and 15, node 30 has children 25 and 40, and node 15 has children 12 and 18. Key 5 is in the left subtree of 10 and key 12 is in its right subtree, so 10 is the deepest node above both. **Example 2** ```text Input: root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 15, q = 12 Output: 15 ``` Node 15 is the parent of 12, and a node counts as part of its own subtree. **Example 3** ```text Input: root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 18, q = 25 Output: 20 ``` Key 18 is in the root's left subtree and key 25 is in its right subtree, so only the root contains both.

Overview: Given a binary search tree in level-order form and two distinct keys present in it, return the key of their lowest common ancestor, where a node counts as its own ancestor. Tests reasoning with the search tree ordering, plus time and space analysis on skewed trees.

Read the full Amazon Frontend Engineer interview experience this question came from

Given a binary search tree and two distinct keys `p` and `q` that are both in the tree, return the key of their lowest common ancestor: the node farthest from the root whose subtree contains both `p` and `q`. A node's subtree includes the node itself, so if one of the two keys is an ancestor of the other, that key is the answer. **Tree encoding** The tree is given as a level-order list `root`. The first element is the root. Then, for each non-null node in the order it appears, the list gives its left child followed by its right child, with `None` for a missing child (`null` in JavaScript and Java, an empty `std::optional<int>` in C++). Trailing `None` values may be omitted. **Rules** - All keys are distinct. For every node, every key in its left subtree is smaller than the node's key, and every key in its right subtree is larger. - The common ancestors of `p` and `q` all lie on one path from the root, so exactly one of them is farthest from the root. Return its key. - Every key fits in a signed 32-bit integer, so the return type is `int` in Java and C++. Note that the difference of two keys can reach 2 * 10^9, which exceeds 2^31 - 1. **Constraints** - The tree has between `2` and `100000` nodes. - `-10^9 <= key <= 10^9` for every key. - `p != q`, and both `p` and `q` are keys in the tree. - The tree is not necessarily balanced; its height can equal the number of nodes. **Example 1** ```text Input: root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 12, q = 5 Output: 10 ``` The root 20 has children 10 and 30. Node 10 has children 5 and 15, node 30 has children 25 and 40, and node 15 has children 12 and 18. Key 5 is in the left subtree of 10 and key 12 is in its right subtree, so 10 is the deepest node above both. **Example 2** ```text Input: root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 15, q = 12 Output: 15 ``` Node 15 is the parent of 12, and a node counts as part of its own subtree.

Constraints

  • The tree has between 2 and 100000 nodes.
  • -10^9 <= key <= 10^9 for every key.
  • p != q, and both p and q are keys in the tree.
  • All keys are distinct; for every node, every key in its left subtree is smaller than the node's key and every key in its right subtree is larger.
  • The tree is not necessarily balanced; its height can equal the number of nodes.
  • root is a level-order encoding whose first element is the non-null root; trailing None values may be omitted.

Examples

Input: ([20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], 12, 5)

Expected Output: 10

Explanation: Source example 1: 5 and 12 split at node 10, below the root (p > q).

Input: ([20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], 15, 12)

Expected Output: 15

Explanation: Source example 2: 15 is the parent of 12, so the ancestor key itself is the answer.

Hints

  1. Only non-null nodes contribute child slots in the level-order list, so a node's children are not always at positions 2i+1 and 2i+2.
  2. From a node's key alone, the BST ordering tells you which side of that node each of p and q lies on. Remember that a node counts as part of its own subtree.
  3. The tree can be a single chain of 100000 nodes, so do not rely on the tree being balanced or on deep recursion.

Loading coding console...

Show the approach

Approach

Decode the list, then walk down from the root.

Decoding: keep a pointer nxt to the next unread slot, starting at index 1. Visit the list in order, and for every non-null entry consume up to two slots from nxt as its left and right child. A None slot means no child, and a slot past the end of the list is an omitted trailing None. Non-null entries appear in breadth-first order, so this reproduces the encoding exactly. A fixed 2i+1 / 2i+2 formula does not, because missing nodes have no child slots.

Walk: let lo = min(p, q) and hi = max(p, q). At the current node, if hi is smaller than its key, both keys are in the left subtree, so move left. If lo is larger than its key, both are in the right subtree, so move right. Otherwise stop and return the current key.

Invariant: the current node's subtree contains both p and q. It holds at the root, and each move keeps it because the BST ordering puts every key smaller than a node in its left subtree and every larger key in its right subtree. When the walk stops, either lo < key < hi, so p and q lie in different child subtrees and no child contains both, or the key equals p or q, so no proper descendant contains that key. Either way the current node is the deepest node whose subtree holds both keys, which the statement guarantees is unique.

Edge cases: the answer may be p or q itself, including the root; argument order does not matter because of min/max; omitted trailing None values are handled by the bounds check on nxt; the tree may be a single chain of 100000 nodes, so both phases are iterative rather than recursive; keys are compared directly rather than subtracted, because the difference of two keys can reach 2 * 10^9 and overflow a 32-bit int.

Time complexity:
O(n)
Space complexity:
O(n)