Find the Lowest Common Ancestor of Two Nodes in a Binary Search Tree

Problem and examples

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.

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.

How it works

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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* current = root;
    while (current) {
        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 nullptr;
}

int main() {
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);
    TreeNode* p = root->left;
    TreeNode* q = root->left->right;
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    cout << "Lowest Common Ancestor: " << lca->val << endl;
    return 0;
}

Python implementation

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

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

if __name__ == '__main__':
    root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(9)
    p = root.left
    q = root.left.right
    lca = lowestCommonAncestor(root, p, q)
    print("Lowest Common Ancestor:", lca.val)

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class LowestCommonAncestorBST {
    public 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;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        TreeNode p = root.left;
        TreeNode q = root.left.right;
        LowestCommonAncestorBST sol = new LowestCommonAncestorBST();
        TreeNode lca = sol.lowestCommonAncestor(root, p, q);
        System.out.println("Lowest Common Ancestor: " + lca.val);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root, p, q) {
    let current = root;
    while (current) {
        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;
}

const root = new TreeNode(6);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);
const p = root.left;
const q = root.left.right;
const lca = lowestCommonAncestor(root, p, q);
console.log("Lowest Common Ancestor:", lca.val);

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    current := root
    for current != nil {
        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 nil
}

func main() {
    root := &TreeNode{Val: 6}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 0}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right.Left = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 9}
    p := root.Left
    q := root.Left.Right
    lca := lowestCommonAncestor(root, p, q)
    fmt.Println("Lowest Common Ancestor:", lca.Val)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn lowest_common_ancestor(
    mut root: &TreeNode,
    p: i32,
    q: i32
) -> &TreeNode {
    loop {
        if p < root.val && q < root.val {
            root = root.left.as_ref().unwrap();
        } else if p > root.val && q > root.val {
            root = root.right.as_ref().unwrap();
        } else {
            return root;
        }
    }
}

Kotlin implementation

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
    var current = root
    while (current != null) {
        current = when {
            p.`val` < current.`val` && q.`val` < current.`val` -> current.left
            p.`val` > current.`val` && q.`val` > current.`val` -> current.right
            else -> return current
        }
    }
    return null
}

fun main() {
    val root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left!!.left = TreeNode(0)
    root.left!!.right = TreeNode(4)
    root.right!!.left = TreeNode(7)
    root.right!!.right = TreeNode(9)
    val p = root.left!!
    val q = root.left!!.right!!
    val lca = lowestCommonAncestor(root, p, q)
    println("Lowest Common Ancestor: ${lca?.`val`}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
    var current = root
    while let node = current {
        if p.val < node.val && q.val < node.val {
            current = node.left
        } else if p.val > node.val && q.val > node.val {
            current = node.right
        } else {
            return node
        }
    }
    return nil
}

let root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left?.left = TreeNode(0)
root.left?.right = TreeNode(4)
root.right?.left = TreeNode(7)
root.right?.right = TreeNode(9)
let p = root.left!
let q = root.left!.right!
if let lca = lowestCommonAncestor(root, p, q) {
    print("Lowest Common Ancestor: \(lca.val)")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode | null {
    let current: TreeNode | null = root;
    while (current) {
        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;
}

const root = new TreeNode(6);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);
const p = root.left!;
const q = root.left!.right!;
const lca = lowestCommonAncestor(root, p, q);
console.log("Lowest Common Ancestor:", lca!.val);