Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Medium

Lowest Common Ancestor of a BST

Lowest common ancestor of a BST explained: walk down until p and q split sides, an O(h) tested Python solution, common pitfalls and a live BST visual.

Also searched as: LCA in a binary search tree · lowest common ancestor BST iterative

🌳

Try it live Free

Binary Search Tree & Traversals

Insert values in the BST lab and trace the search paths to two values: the last node both paths share is their lowest common ancestor.

Open the playground →

The problem

Given a binary search tree and two nodes p and q that exist in it, return their lowest common ancestor: the deepest node that has both p and q in its subtree (a node counts as its own descendant).

Inputroot = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output6
Inputsame tree, p = 2, q = 4
Output2

2 is an ancestor of 4, so it is the LCA.

The key insight

The BST ordering tells you where both nodes live without searching. If both values are smaller than the current node, the LCA is in the left subtree; if both are larger, it is in the right. The first node where they split (or where one of them equals the current node) is the answer.

Brute force first: Ignoring the BST property and using the general binary-tree LCA works in O(n), but the ordering lets you do it in O(h).

Step-by-step approach

  1. Start at the root.
  2. If both p.val and q.val are less than node.val, move left.
  3. If both are greater than node.val, move right.
  4. Otherwise they split here (or one equals this node): return the current node.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def lowest_common_ancestor_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node                # p and q split here (or one is node)
    return None

Complexity

TimeO(h)
SpaceO(1)

You walk a single root-to-node path, so time is the height h: O(log n) for a balanced BST. The iterative loop uses constant extra space.

Common mistakes

Frequently asked questions

What is the time and space complexity of LCA in a BST?

O(h) time, following one path from the root, and O(1) space for the iterative version. For a balanced BST h is about log n.

What if p or q might not be in the tree?

The basic version assumes both exist. If not guaranteed, search for each value first, or confirm the returned node's subtree really contains both.

How is this different from LCA in a general binary tree?

Without ordering you cannot tell which side a value is on, so you must search both subtrees recursively, which costs O(n).

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.