Lowest Common Ancestor (LCA) in Binary Trees & BSTs

The lowest common ancestor (LCA) of two nodes p and q is the deepest node in the tree that has both p and q as descendants (a node is allowed to be a descendant of itself). LCA is a classic interview problem with two clean solutions: a fast O(h) one that exploits the BST ordering, and a general O(n) one for any binary tree.

We reuse the standard TreeNode.

LCA in a BST — use the ordering

In a BST you don’t need to search; the values tell you which way to go. Starting at the root:

If both p and q are smaller than the current node, the LCA is in the left subtree.
If both are larger, it’s in the right subtree.
Otherwise they split here (one on each side, or one equals this node) — the current node is the LCA.

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

TreeNode lcaBST(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; // split point
    }
    return null;
}

function lcaBST(root, p, 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; // split point
  }
  return null;
}

def lca_bst(root, p, q):
    while root is not None:
        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  # split point
    return None

This is O(h) time — O(log n) on a balanced BST — and O(1) space.

LCA in a general binary tree

Without ordering, you can’t pick a direction, so search both sides. The recursion returns:

The node itself if it equals p or q.
If both left and right recursions find something, the current node is the LCA (the targets split here).
Otherwise propagate up whichever side found a target.

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) return root;
    TreeNode* left  = lca(root->left, p, q);
    TreeNode* right = lca(root->right, p, q);
    if (left != nullptr && right != nullptr) return root; // split here
    return left != nullptr ? left : right;
}

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left  = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left != null && right != null) return root; // split here
    return left != null ? left : right;
}

function lca(root, p, q) {
  if (root === null || root === p || root === q) return root;
  const left  = lca(root.left, p, q);
  const right = lca(root.right, p, q);
  if (left !== null && right !== null) return root; // split here
  return left !== null ? left : right;
}

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left is not None and right is not None:
        return root  # split here
    return left if left is not None else right

This is O(n) time (it may visit every node) and O(h) space for recursion.

For beginners: The BST version compares values; the general version compares node identity (root == p). That difference matters when a tree contains duplicate values.

Complexity comparison

Tree type	Time	Space
BST (use ordering)	O(h) → O(log n) balanced	O(1) iterative
General binary tree	O(n)	O(h) recursion

Going deeper: When you must answer many LCA queries on a static tree, preprocess with binary lifting or an Euler-tour + sparse table to answer each query in O(log n) or O(1) after O(n log n) setup.

Common pitfall

Assuming both p and q are actually present in the tree. If one might be missing, the general algorithm can return a non-ancestor; verify presence first, or adapt the recursion to confirm both targets were found.

Next steps

You’ve finished the core tree algorithms. Lock them in with the tree exercises and check your work against the tree solutions.