Find LCA in a BST

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Find LCA in a BST

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

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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Choose traversal based on the required output. DFS is natural for subtree computations, reconstruction, and range pruning; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.