Lowest Common Ancestor in a Binary Search Tree

Last Updated : 11 Oct, 2025

Given the root of a Binary Search Tree and two node n1 and n2, find the Lowest Common Ancestor (LCA). LCA is the deepest node that has both n1 and n2 as descendants.

Note: Both node are always present in the Binary Search Tree.

Examples: 

Input:  n1.data = 4, n2.data = 14

lowest_common_ancestor_in_a_binary_tree2

Output: 8
Explanation: 8 is the lowest common ancestor (LCA) of nodes 4 and 14, as it is the deepest node that is an ancestor of both.

lowest_common_ancestor_in_a_binary_tree_2

Input: n1.data = 10, n2.data = 14

lowest_common_ancestor_in_a_binary_tree2

Output: 12
Explanation: 12 is the lowest common ancestor (LCA) of nodes 10 and 14, as it is the deepest node that is an ancestor of both.

lowest_common_ancestor_in_a_binary_tree_4
Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] LCA by Normal Binary Tree Methods - O(n) Time and O(n) Space

We can use any of the approaches discussed in Lowest Common Ancestor in a Binary Tree, which run in O(n) time, where n is the number of nodes in the BST. However, we can achieve a better time complexity by leveraging the properties of the BST.

[Better Approach] Using BST Properties (Recursive Approach) - O(h) Time and O(h) Space

This approach is based on the observation that the LCA is the lowest (closest to root) node whose value lies between n1 and n2.

In a Binary search tree, while traversing the tree from top to bottom the first node which lies in between the two numbers n1 and n2 is the LCA of the nodes, i.e. the first node n with the lowest depth which lies in between n1 and n2 (n1 <= n <= n2, assuming n1 < n2). 

So, we just recursively traverse the BST , if node's value is greater than both n1 and n2 then our LCA lies in the left side of the node, if it is smaller than both n1 and n2, then LCA lies on the right side. Otherwise, the root is LCA (assuming that both n1 and n2 are present in BST).

C++ 
//Driver Code Starts
#include <iostream>
using namespace std;

// Node structure
class Node {
  public:
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};
//Driver Code Ends


Node* LCA(Node* root, Node* n1, Node* n2) {
  	
    if (root == nullptr)
        return nullptr;

    // If both n1 and n2 are smaller than 
    // root, go to left subtree
    if (root->data > n1->data && root->data > n2->data)
        return LCA(root->left, n1, n2);

    // If both n1 and n2 are greater than 
    // root, go to right subtree
    if (root->data < n1->data && root->data < n2->data)
        return LCA(root->right, n1, n2);

    // If nodes n1 and n2 are on the opposite sides, 
    // then root is the LCA
    return root;
}


//Driver Code Starts
int main() {
  	
  	// Representation of input BST:
    //            20
    //           /  \
    //          8    22
    //        /   \     
    //       4    12   
    //           /   \    
    //         10    14  
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // Node 4
    Node* n1 = root->left->left; 
    
    // Node 14
    Node* n2 = root->left->right->right; 

    Node* res = LCA(root, n1, n2);
    cout << res->data << endl;

    return 0;
}

//Driver Code Ends
C 
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->left = node->right = NULL;
    return node;
}
//Driver Code Ends


Node* LCA(Node* root, Node* n1, Node* n2) {
    if (root == NULL)
        return NULL;

    // If both n1 and n2 are smaller than root, 
  	// go to left subtree
    if (root->data > n1->data && root->data > n2->data)
        return LCA(root->left, n1, n2);

    // If both n1 and n2 are greater than root, 
  	// go to right subtree
    if (root->data < n1->data && root->data < n2->data)
        return LCA(root->right, n1, n2);

    // If nodes n1 and n2 are on the opposite sides, 
  	// root is the LCA
    return root;
}


//Driver Code Starts
int main() {
    // Representation of input BST:
    //            20
    //           /  \
    //          8    22
    //        /   \     
    //       4    12   
    //           /   \   
    //         10    14  
    Node* root = newNode(20);
    root->left = newNode(8);
    root->right = newNode(22);
    root->left->left = newNode(4);
    root->left->right = newNode(12);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);

    // Node 4
    Node* n1 = root->left->left; 
    
    // Node 14
    Node* n2 = root->left->right->right; 
  
    Node* res = LCA(root, n1, n2);
    printf("%d
", res->data);

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
// Node structure
class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class GFG {
//Driver Code Ends

    
    static Node LCA(Node root, Node n1, Node n2) {
        if (root == null)
            return null;

        // If both n1 and n2 are smaller than root, 
      	// go to left subtree
        if (root.data > n1.data && root.data > n2.data)
            return LCA(root.left, n1, n2);

        // If both n1 and n2 are greater than root, 
      	// go to right subtree
        if (root.data < n1.data && root.data < n2.data)
            return LCA(root.right, n1, n2);

        // If nodes n1 and n2 are on the opposite sides, 
  	    // root is the LCA
        return root;
    }


//Driver Code Starts
    public static void main(String[] args) {
        // Representation of input BST:
        //            20
        //           /  \
        //          8    22
        //        /   \     
        //       4    12   
        //           /   \   
        //         10    14  
        
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);

        // Node 4
        Node n1 = root.left.left; 
        
        // Node 14
        Node n2 = root.left.right.right; 
      
        Node res = LCA(root, n1, n2);
        System.out.println(res.data);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
# Node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

#Driver Code Ends


def LCA(root, n1, n2):
    if root is None:
        return None

    # If both n1 and n2 are smaller than root, 
    # go to left subtree
    if root.data > n1.data and root.data > n2.data:
        return LCA(root.left, n1, n2)

    # If both n1 and n2 are greater than root, 
    # go to right subtree
    if root.data < n1.data and root.data < n2.data:
        return LCA(root.right, n1, n2)

    # If nodes n1 and n2 are on the opposite sides, 
    # root is the LCA
    return root


#Driver Code Starts
if __name__ == "__main__":
    # Representation of input BST:
    #            20
    #           /  \
    #          8    22
    #        /   \     
    #       4    12   
    #           /   \   
    #         10    14  
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)

    # Node 4
    n1 = root.left.left  
    
    # Node 14
    n2 = root.left.right.right 
    
    res = LCA(root, n1, n2)
    print(res.data)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class GFG {
    
//Driver Code Ends

    static Node LCA(Node root, Node n1, Node n2) {
        if (root == null)
            return null;

        // If both n1 and n2 are smaller than root,
      	// go to left subtree
        if (root.data > n1.data && root.data > n2.data)
            return LCA(root.left, n1, n2);

        // If both n1 and n2 are greater than root, 
      	// go to right subtree
        if (root.data < n1.data && root.data < n2.data)
            return LCA(root.right, n1, n2);

        // If nodes n1 and n2 are on the opposite sides, 
      	// root is the LCA
        return root;
    }

//Driver Code Starts

    static void Main(string[] args) {
        // Representation of input BST:
        //            20
        //           /  \
        //          8    22
        //        /   \     
        //       4    12   
        //           /   \   
        //         10    14  
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);

        // Node 4
        Node n1 = root.left.left; 
        
        // Node 14
        Node n2 = root.left.right.right; 
      
        Node res = LCA(root, n1, n2);
        Console.WriteLine(res.data);
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
// Node structure
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


function LCA(root, n1, n2) {
    if (root === null)
        return null;

    // If both n1 and n2 are smaller than root, go to left subtree
    if (root.data > n1.data && root.data > n2.data)
        return LCA(root.left, n1, n2);

    // If both n1 and n2 are greater than root, go to right subtree
    if (root.data < n1.data && root.data < n2.data)
        return LCA(root.right, n1, n2);

    // If nodes n1 and n2 are on the opposite sides, root is the LCA
    return root;
}


//Driver Code Starts
// Driver Code

// Representation of input BST:
//            20
//           /  \
//          8    22
//        /   \     
//       4    12   
//           /   \   
//         10    14  
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Node 4
const n1 = root.left.left; 

// Node 14
const n2 = root.left.right.right;

const res = LCA(root, n1, n2);
console.log(res.data);

//Driver Code Ends

Output
8

[Expected Approach] Using BST Properties (Iterative Method) - O(h) Time and O(1) Space

The auxiliary space in the above method can be optimized by eliminating recursion. Below is the iterative implementation of this approach.

C++ 
//Driver Code Starts
#include <iostream>
using namespace std;

// Node structure
class Node {
  public:
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};
//Driver Code Ends


Node* LCA(Node* root, Node* n1, Node* n2) {

    while (root != nullptr) {
      
        // If both n1 and n2 are smaller than root,
        // then LCA lies in left
        if (root->data > n1->data && root->data > n2->data)
            root = root->left;

        // If both n1 and n2 are greater than root,
        // then LCA lies in right
        else if (root->data < n1->data && root->data < n2->data)
            root = root->right;
        
        // Else Ancestor is found
        else
            break;
    }

    return root;
}


//Driver Code Starts
int main() {
  	
  	// Representation of input BST:
    //            20
    //           /  \
    //          8    22
    //        /   \     
    //       4    12   
    //           /   \   
    //         10    14  
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // Node 4
    Node* n1 = root->left->left; 
    
    // Node 14
    Node* n2 = root->left->right->right; 

    Node* res = LCA(root, n1, n2);
    cout << res->data << endl;

    return 0;
}

//Driver Code Ends
C 
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}
//Driver Code Ends


Node* LCA(Node* root, Node* n1, Node* n2) {
    while (root != NULL) {
        
        // If both n1 and n2 are smaller than root,
        // then LCA lies in left
        if (root->data > n1->data && root->data > n2->data)
            root = root->left;

        // If both n1 and n2 are greater than root,
        // then LCA lies in right
        else if (root->data < n1->data && root->data < n2->data)
            root = root->right;

        // Else Ancestor is found
        else
            break;
    }
    return root;
}


//Driver Code Starts
int main() {
    // Representation of input BST:
    //            20
    //           /  \
    //          8    22
    //        /   \     
    //       4    12   
    //           /   \   
    //         10    14  
    Node* root = createNode(20);
    root->left = createNode(8);
    root->right = createNode(22);
    root->left->left = createNode(4);
    root->left->right = createNode(12);
    root->left->right->left = createNode(10);
    root->left->right->right = createNode(14);

    // Node 4
    Node* n1 = root->left->left; 
    
    // Node 14
    Node* n2 = root->left->right->right;

    Node* res = LCA(root, n1, n2);
    printf("%d
", res->data);

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
// Node structure
class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class GFG {
//Driver Code Ends

    
    static Node LCA(Node root, Node n1, Node n2) {
      
        while (root != null) {
          
            // If both n1 and n2 are smaller than root,
            // then LCA lies in left
            if (root.data > n1.data && root.data > n2.data)
                root = root.left;

            // If both n1 and n2 are greater than root,
            // then LCA lies in right
            else if (root.data < n1.data && root.data < n2.data)
                root = root.right;

            // Else Ancestor is found
            else
                break;
        }
      
        return root;
    }

//Driver Code Starts

    public static void main(String[] args) {
        // Representation of input BST:
        //            20
        //           /  \
        //          8    22
        //        /   \
        //       4    12
        //           /   \
        //         10    14
        
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);

        // Node 4
        Node n1 = root.left.left; 
        
        // Node 14
        Node n2 = root.left.right.right; 

        Node res = LCA(root, n1, n2);
        System.out.println(res.data);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
# Node structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

#Driver Code Ends


def LCA(root, n1, n2):
  
    while root:
      
        # If both n1 and n2 are smaller than root,
        # then LCA lies in left
        if root.data > n1.data and root.data > n2.data:
            root = root.left
            
        # If both n1 and n2 are greater than root,
        # then LCA lies in right
        elif root.data < n1.data and root.data < n2.data:
            root = root.right
            
        # Else Ancestor is found
        else:
            break
            
    return root


#Driver Code Starts
if __name__ == "__main__":
    
    # Representation of input BST:
    #            20
    #           /  \
    #          8    22
    #        /   \     
    #       4    12   
    #           /   \   
    #         10    14  
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)

     # Node 4
    n1 = root.left.left 
    
     # Node 14
    n2 = root.left.right.right

    res = LCA(root, n1, n2)
    print(res.data)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class GFG {
//Driver Code Ends


    static Node LCA(Node root, Node n1, Node n2) {
      
        while (root != null) {
          
            // If both n1 and n2 are smaller than root,
            // then LCA lies in left
            if (root.data > n1.data && root.data > n2.data)
                root = root.left;
          	
            // If both n1 and n2 are greater than root,
            // then LCA lies in right
          	
            else if (root.data < n1.data && root.data < n2.data)
                root = root.right;
          	
            // Else Ancestor is found
            else
                break;
        }
      	
        return root;
    }


//Driver Code Starts
    static void Main(string[] args) {
        // Representation of input BST:
        //            20
        //           /  \
        //          8    22
        //        /   \     
        //       4    12   
        //           /   \   
        //         10    14  
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(4);
        root.left.right = new Node(12);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);

        // Node 4
        Node n1 = root.left.left; 
        
        // Node 14
        Node n2 = root.left.right.right; 
        
        Node res = LCA(root, n1, n2);
        Console.WriteLine(res.data);
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
// Node structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


function LCA(root, n1, n2) {

    while (root !== null) {
    
        // If both n1 and n2 are smaller than root,
        // then LCA lies in left
        if (root.data > n1.data && root.data > n2.data) 
            root = root.left;
        
        // If both n1 and n2 are greater than root,
        // then LCA lies in right
        else if (root.data < n1.data && root.data < n2.data) 
            root = root.right;
        
        // Else Ancestor is found
        else 
            break;
    }
    return root;
}


//Driver Code Starts
// Representation of input BST:
//            20
//           /  \
//          8    22
//        /   \     
//       4    12   
//           /   \   
//         10    14  
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Node 4
const n1 = root.left.left; 

// Node 14
const n2 = root.left.right.right; 

const res = LCA(root, n1, n2);
console.log(res.data);

//Driver Code Ends

Output
8

Related Articles:
LCA using Parent Pointer
Find LCA in Binary Tree using RMQ

Comment

Explore