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

Algorithm Steps

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.

Find the Lowest Common Ancestor of Two Nodes in a BST - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

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