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

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❯

Case 1: General Case – Nodes on Different Sides

In a BST, if one node lies in the left subtree and the other in the right, then the current node is the lowest common ancestor. For example, in the tree [6,2,8,0,4,7,9,null,null,3,5], if we look for LCA of 2 and 8, they lie on different sides of 6. So, 6 is the lowest node that connects both branches — the LCA.

Case 2: One Node is Ancestor of the Other

Sometimes, one of the given nodes is actually the ancestor of the other. In BST terms, if both p and q are on the same side and one is directly in the path of the other, then the upper node is the LCA. For instance, in the same tree, the LCA of nodes 2 and 4 is 2 — since 4 is a descendant of 2 and BST traversal leads us to 2 before 4.

Case 3: Both Nodes Are the Same

In this special case, when p == q, the lowest common ancestor is the node itself. The BST structure doesn’t matter in this case — if you are asked for the LCA of a node with itself, the answer is trivially that node.

Case 4: Tree is Empty

If the root of the BST is null, the tree doesn’t contain any nodes. No matter what values p and q are, the answer will be null because there's no structure to even begin a search. This case should be handled upfront to avoid null pointer issues during traversal.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         6
    #        / \
    #       2   8
    #      / \  / \
    #     0  4 7   9
    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           # Node with value 2
    q = root.left.right     # Node with value 4
    lca = lowestCommonAncestor(root, p, q)
    print(lca.val)  # Output should be 2