Lowest common ancestor in a BST

Find the deepest node that has both given keys beneath it (or is one of them).

Time O(h)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Walk down from the root. While both keys are on the same side, follow them. The first node where they split, or that equals one of them, is their lowest common ancestor.

Code

C++PythonC#

TreeNode* lca(TreeNode* root, int p, int q) {
    while (root) {
        if (p < root->val && q < root->val) root = root->left;
        else if (p > root->val && q > root->val) root = root->right;
        else return root;
    }
    return nullptr;
}

def lca(root: TreeNode | None, p: int, q: int) -> TreeNode | None:
    while root:
        if p < root.val and q < root.val: root = root.left
        elif p > root.val and q > root.val: root = root.right
        else: return root
    return None

public static TreeNode Lca(TreeNode root, int p, int q) {
    while (root != null) {
        if (p < root.val && q < root.val) root = root.left;
        else if (p > root.val && q > root.val) root = root.right;
        else return root;
    }
    return null;
}

Tips

This shortcut only works because of BST ordering. A general binary tree needs a full postorder search.

In the .NET library

SortedSet<T>.GetViewBetween(lo, hi) relies on the same split-point idea to return a range without scanning the whole tree.