Lowest Common Ancestor in BST - Algorithm, Visualization, Code Examples

Binary Search Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given the root of a Binary Search Tree (BST) and two nodes p and q, find the lowest common ancestor (LCA) of the two nodes. The lowest common ancestor is the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Assumptions:

  • All node values are unique.
  • p and q are guaranteed to exist in the BST.

Examples❯

Input Tree Node 1 Node 2 Lowest Common Ancestor Description
[20, 10, 30, 5, 15, 25, 35]
5 15 10 Both nodes lie in the left subtree of 20; 10 is their direct parent.
[20, 10, 30, 5, 15, 25, 35]
5 35 20 Nodes are on opposite sides of root (left and right); LCA is the root 20.
[20, 10, 30, 5, 15, null, null]
15 30 20 15 is in left subtree, 30 in right; LCA is the first split node: 20.
[10, 5, 15, null, null, null, 20]
15 20 15 20 is a right child of 15, so LCA is 15 itself.
[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
3 5 4 3 and 5 are children of 4; LCA is their direct parent node 4.

Solution❯

Understanding the Problem

We are given a Binary Search Tree (BST) and two nodes p and q. Our goal is to find their Lowest Common Ancestor (LCA). In a BST, the LCA of two nodes is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Because this is a BST, the left child of a node is always smaller and the right child is always larger. We can use this property to efficiently find the LCA by comparing p and q with the current node while traversing.

Step-by-Step Solution with Example

Step 1: Understand the structure of BST

Let’s use the following BST as an example:

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

Step 2: Compare nodes with current root

We start from the root node (6). Suppose we are asked to find the LCA of nodes 2 and 8.

Since 2 < 6 and 8 > 6, they lie on different sides of 6. That means 6 is the first node that splits their paths — this is our LCA.

Step 3: Move left or right if both nodes are on same side

Now suppose we are looking for the LCA of nodes 2 and 4. Both nodes are < 6, so we move left to node 2.

At node 2, we check again: 2 == p and 4 is in the right subtree — so 2 is the ancestor of 4. That means 2 is the LCA.

Step 4: If the current node is equal to one of the targets

Now let’s say we look for the LCA of node 2 and node 2 (both are the same). Here, since both nodes are equal, the LCA is just node 2.

Step 5: Return null if tree is empty

If the tree is empty (i.e., the root is null), we cannot find an ancestor. So, we immediately return null.

Edge Cases

Case 1: Nodes on different sides

This is the most common case. If p < root < q or q < root < p, then the current root is the LCA.

Case 2: One node is ancestor of the other

If one node lies directly in the path of the other, then that node is the LCA. For example, LCA of 2 and 4 is 2.

Case 3: Both nodes are the same

If p == q, then the LCA is just that node. This should be explicitly checked to avoid unnecessary traversal.

Case 4: Tree is empty

If root is null, return null immediately — the tree doesn't contain any nodes.

Finally

By taking advantage of the BST properties, we can find the LCA in O(h) time, where h is the height of the tree. Always check for the edge cases — especially null roots or when both nodes are the same. For beginners, the key intuition is to imagine how you'd search for each node in a BST. The first split point during this process is your lowest common ancestor.

Algorithm Steps❯

  1. Given a binary search tree (BST) and two nodes, p and q.
  2. Start at the root of the BST.
  3. If both p and q are less than the current node, move to the left child.
  4. If both p and q are greater than the current node, move to the right child.
  5. Otherwise, the current node is the lowest common ancestor (LCA) of p and q.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

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

int main() {
    TreeNode* root = createNode(6);
    root->left = createNode(2);
    root->right = createNode(8);
    root->left->left = createNode(0);
    root->left->right = createNode(4);
    root->right->left = createNode(7);
    root->right->right = createNode(9);
    TreeNode* p = root->left;
    TreeNode* q = root->left->right;
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    printf("Lowest Common Ancestor: %d\n", lca->val);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...