Lowest Common Ancestor in Binary Search Tree (BST)

Introduction

The Lowest Common Ancestor (LCA) problem is an important and frequently asked DSA interview question related to trees. While the basic idea looks simple, interviewers often expect a deep understanding of logic, edge cases, and BST properties.

In simple words, the Lowest Common Ancestor of two nodes is the lowest (closest) node in the tree that connects both nodes.

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a binary tree that follows a strict ordering rule:

• All nodes in the left subtree have values less than the root

• All nodes in the right subtree have values greater than the root

Because of this property:

• Searching becomes faster

• Many problems (including LCA) become easier

Understanding this rule is the key to solving the LCA problem efficiently.

What is the Lowest Common Ancestor?

The Lowest Common Ancestor of two nodes p and q is defined as:

The lowest node in the tree that has both p and q as its descendants.

Important points to understand clearly:

• A node can be a descendant of itself

• The LCA is always unique

• The LCA does not have to be the root

Real-Life Example to Understand LCA

Think of a family tree:

• Two cousins meet at their grandparent

• Two siblings meet at their parent

That meeting point is similar to the Lowest Common Ancestor in a tree.

Example Tree

Consider the following BST:

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

If:

• p = 2 and q = 8 → LCA = 6

• p = 2 and q = 4 → LCA = 2

• p = 3 and q = 5 → LCA = 4

Why BST Property Makes LCA Easy

In a normal binary tree, finding LCA requires extra work.

But in a BST, values guide us:

• If both values are smaller than current node → move left

• If both values are greater than current node → move right

• If values lie on different sides → current node is LCA

This reduces unnecessary traversal.

Detailed Step-by-Step Explanation

Let current node be root.

1. Compare values of p and q with root

2. If both are smaller than root, search in left subtree

3. If both are greater than root, search in right subtree

4. If one is smaller and the other is larger, root is the LCA

5. Stop traversal once LCA is found

This logic works because BST values are ordered.

Detailed Dry Run Example

Let p = 2 and q = 8

Current Node	p < node	q > node	Decision
6	Yes	Yes	LCA found

Answer = 6

Another example:

Let p = 3 and q = 5

Current Node	Decision
6	Both smaller → go left
2	Both greater → go right
4	One left, one right → LCA

Answer = 4

Recursive Approach Explanation

The recursive solution follows the same logic naturally.

• Each recursive call moves closer to the LCA

• Recursion stops when the correct node is found

C++ Recursive Code

Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (root == NULL) return NULL;

    if (p->data < root->data && q->data < root->data)
        return lowestCommonAncestor(root->left, p, q);

    if (p->data > root->data && q->data > root->data)
        return lowestCommonAncestor(root->right, p, q);

    return root;
}

Iterative Approach (Often Asked in Interviews)

Some interviewers ask for a non-recursive solution.

Iterative Logic

• Start from root

• Move left or right based on values

• Stop when LCA is found

C++ Iterative Code

Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    while (root != NULL) {
        if (p->data < root->data && q->data < root->data)
            root = root->left;
        else if (p->data > root->data && q->data > root->data)
            root = root->right;
        else
            return root;
    }
    return NULL;
}

Java Code

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

Python Code

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

Time and Space Complexity (Detailed)

• Time Complexity: O(h)

  • h is height of BST

  • Balanced tree → O(log n)

  • Skewed tree → O(n)

• Space Complexity:

  • Recursive → O(h)

  • Iterative → O(1)

Important Edge Cases (Interview Favorite)

• Tree contains only one node

• One node is ancestor of the other

• p and q are same node

• Tree is skewed (like a linked list)

Always discuss these cases in interviews.

Difference Between LCA in BST and Binary Tree

LCA in BST	LCA in Binary Tree
Uses ordering property	No ordering property
Faster	Slower
Simple logic	More complex

Interviewers often ask this comparison.

Common Interview Follow-Up Questions

• Can you solve LCA without recursion?

• How to find LCA in a normal binary tree?

• What if parent pointer is given?

• What if nodes do not exist in tree?

Being prepared for these increases confidence.

Summary

The Lowest Common Ancestor in a Binary Search Tree is a powerful problem that becomes simple once BST properties are understood clearly. By comparing node values and moving left or right accordingly, we can find the LCA efficiently without scanning the entire tree. Understanding both recursive and iterative approaches, handling edge cases, and explaining time complexity clearly will help you confidently solve this problem in technical interviews.