LCA BST

Python data engineering interview problem. Difficulty: advanced. Pattern: Trees. About 18 minutes. Part of the Pro drill bank.

Lowest common ancestor in a BST given as level-order. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

In a binary search tree, all values on one side of a node are smaller and values on the other side are larger. That ordering lets you find a shared ancestor without scanning every branch. Return the lowest node that is an ancestor of both values p and q in the BST. A node can be an ancestor of itself. Write lowest_common_ancestor(level_order: list, p: int, q: int) -> int. For p 2 and q 8 in the sample tree, the root 6 is the first node between them, so the answer is 6. The starter file already has the function name and harness print lines. Keep them and fill only the function body.

Requirements

• Use the BST ordering to choose left or right.
• Return the lowest shared ancestor value.
• Handle one target being an ancestor of the other.

Constraints

• The tree is a valid BST represented in level order.
• The return type is an integer node value.

Examples

Input: lowest_common_ancestor([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], 2, 8) Output: 6 2 and 8 split at root.

Topics: lakebench, python, bst, lca.

More Python interview questions · All interview problems · Learn data engineering