Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

The problem in plain language

Given a binary search tree and two different nodes p and q that are known to be in it, find their lowest common ancestor. This is the deepest node whose subtree contains both targets. A target may be its own ancestor, so if p is above q, the answer can be p itself.

A general binary-tree solution can inspect both sides of many nodes, but that would ignore the ordering that makes this tree special. In a binary search tree, every value in a node’s left subtree is smaller than the node’s value, and every value in its right subtree is larger. That fact turns the problem into a single directed walk from the root.

Deriving the optimal approach

Suppose the two target values are ordered as lower and upper. At any current node, only three situations are possible:

  • If the current value is smaller than lower, both targets must be in the right subtree.
  • If the current value is larger than upper, both targets must be in the left subtree.
  • Otherwise, the current value lies between the two targets, inclusive. The targets split across its two sides, or the current node is one of the targets. In either case, the current node is their lowest common ancestor.

Why is the first split point the lowest common ancestor? Before reaching it, both targets are on the same side of every visited node, so the search can safely discard the other side and move deeper. At the first node where the targets no longer belong strictly to one side, no descendant can contain them both. That node is therefore the deepest shared ancestor.

The search touches one node per level and never backtracks. If the tree height is h, it takes O(h) time and O(1) extra space. This is O(log n) time for a balanced tree and O(n) for a completely skewed tree. The algorithm does not modify the tree.

Python solution

from __future__ import annotations

from typing import Optional


class TreeNode:
    """A node in a binary search tree."""

    def __init__(
        self,
        val: int = 0,
        left: Optional[TreeNode] = None,
        right: Optional[TreeNode] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def lowestCommonAncestor(
        self,
        root: Optional[TreeNode],
        p: Optional[TreeNode],
        q: Optional[TreeNode],
    ) -> TreeNode:
        """Return the lowest BST node whose subtree contains p and q."""
        if root is None or p is None or q is None:
            raise ValueError("root, p, and q must all be non-null")

        lower_value, upper_value = self._ordered_target_values(p, q)
        current: Optional[TreeNode] = root

        while current is not None:
            if current.val < lower_value:
                # Both targets are larger, so they must share the right side.
                current = current.right
            elif current.val > upper_value:
                # Both targets are smaller, so they must share the left side.
                current = current.left
            else:
                # The targets split here, or this node is one of the targets.
                return current

        # The problem guarantees that both targets exist in the BST. This
        # explicit failure keeps the method safe when reused with other input.
        raise ValueError("p and q must both be present in the BST")

    @staticmethod
    def _ordered_target_values(p: TreeNode, q: TreeNode) -> tuple[int, int]:
        """Return the target values from smaller to larger."""
        if p.val <= q.val:
            return p.val, q.val
        return q.val, p.val

Interview follow-ups

Can you write the solution recursively?

At each node, make the same comparison as the iterative solution. Recurse right when both targets are larger, recurse left when both are smaller, and return the current node when the targets split or one equals the current node.

The proof and O(h) time bound are unchanged because only one root-to-leaf path is explored. The recursion uses O(h) call-stack space, however, while the iterative version uses O(1) auxiliary space. A skewed tree with many nodes can also exceed Python’s recursion limit, so iteration is the safer production choice.

What if the input is an ordinary binary tree rather than a BST?

The ordering comparisons no longer reveal which direction contains both targets. Use postorder depth-first search instead. A recursive call returns a target when it finds one, returns the non-null result when only one subtree contains a target, and returns the current node when the left and right subtrees each return a non-null result.

The first node that combines discoveries from both sides is the lowest common ancestor; if a node is itself one target and its subtree contains the other, that target correctly propagates upward as the answer. This takes O(n) time because the search may inspect every node and O(h) call-stack space. An iterative parent map is an alternative with O(n) additional storage.

What if either target might be absent from the BST?

The split-point algorithm relies on the original guarantee that both targets exist. Without it, a plausible split can be found even though one target is missing. First search for each target from the root using BST comparisons, checking node identity when the API supplies node objects rather than only values. Return no result or raise an error unless both searches succeed; otherwise run the normal LCA walk.

Each membership search and the final LCA search takes O(h) time, which is still O(h) overall, and the iterative version keeps O(1) extra space. The important tradeoff is a few additional passes in exchange for a correct absence contract.

What if duplicate values are allowed?

Value comparisons alone are no longer enough to identify a node or even to choose a unique direction when a target value equals the current value. The interviewer must first define how duplicates are inserted—for example, always to the left—and whether targets are identified by value or by object identity.

If exact node objects are the targets, the safest general solution is the ordinary-binary-tree LCA algorithm, which uses identity and takes O(n) time with O(h) recursion space. A consistent duplicate-placement rule can sometimes preserve a directed BST search, but equal-valued chains still require extra identity-aware navigation. The original O(h) shortcut depends on unique values.

How would you support many LCA queries on a static tree?

For a small number of queries, repeating this BST walk is attractive because each query already costs only O(h) time and O(1) space. For a very large static tree with many arbitrary-node queries, preprocess each node’s depth and ancestors at powers of two using binary lifting. To answer a query, lift the deeper node to the same depth, then lift both nodes together from the largest jump downward until their parents match.

Binary lifting costs O(n log n) preprocessing time and space, then answers each query in O(log n) time. An Euler tour plus a range-minimum-query structure is another option, with different preprocessing and query tradeoffs. These structures are useful when query volume justifies substantially more memory and setup than the one-query BST solution.

What changes if the tree is frequently updated?

A plain BST can become skewed after insertions, degrading each search and LCA query to O(n). Use a self-balancing BST, such as an AVL or red-black tree, so insertions, deletions, membership checks, and the split-point LCA walk remain O(log n).

If the repeated-query solution also stores parent pointers, depths, or jump tables, every structural update must keep that metadata consistent. Rotations can update local parent and depth relationships, but maintaining global binary-lifting data under arbitrary updates is much more involved. For a dynamic workload, the simpler O(log n) walk on a balanced BST is often preferable unless query latency is exceptionally strict.