Design and analyze the efficiency of an algorithm to find the Lowest Common Ancestor (LCA) in a Binary Search Tree.

Instruction: Assume a valid BST with distinct keys and both requested key values present. Design an iterative LCA algorithm, analyze its dependence on tree height, and explain how the contract changes when a key may be absent.

Context: This question assesses the candidate's understanding of Binary Search Trees (BST) and their ability to apply efficient search techniques. Candidates are expected to outline an algorithm that navigates the structure of a BST to find the lowest common ancestor of two given nodes, considering the properties that define BSTs. Additionally, they should analyze the time complexity of their proposed solution.

Updated

Official answer

Assume a valid BST with distinct keys and that both requested keys are present. A node counts as its own descendant. Nodes expose key, left and right attributes:

def lca_bst(root, p, q):
    low, high = min(p, q), max(p, q)
    node = root
    while node is not None:
        if high < node.key:
            node = node.left
        elif low > node.key:
            node = node.right
        else:
            return node
    return None

If both keys are smaller, their LCA lies in the left subtree; if both are larger, it lies in the right. The first node between the keys is the split point or one of the requested nodes, so it is their lowest common ancestor.

This takes O(h) time and O(1) auxiliary space for height h. Choosing a subtree does not necessarily discard half the nodes: a skewed BST has h=O(n), while a balanced one has h=O(log n).

If membership is not guaranteed, first search for both keys and return no LCA when either is absent; otherwise this algorithm can return a split point for nonexistent keys. Duplicate-key trees require a stated identity/insertion policy rather than this distinct-value contract. Test equal keys, an ancestor/descendant pair, opposite subtrees and a skewed tree.

Related Questions