LCA in Binary Search Tree

Problem Statement: Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Examples

Example 1:

Input Format

Binary Search Tree: 6 2 8 0 4 7 9 -1 -1 3 5 -1 -1 -1 -1

Find LCA of Nodes: 0, 5

Output: Lowest Common Ancestor of 0 and 5 is 2.

Explanation: In the traversal of 0 and 5 back to the root node, 2 is the first common ancestor encountered. This is also the point where their routes upward converged.

Example 2:

Input Format

Binary Search Tree: 10 4 13 4 8 11 15 1 -1 6 9 -1 -1 -1 -1 -1 2 5 7 -1 -1

Find LCA of Nodes: 5, 9

Output: Lowest Common Ancestor of 5 and 9 is 8.

Explanation:  In the traversal of 5 and 9 back to the root node, 8 is the first common ancestor encountered. This is also the point where their routes upwards converged.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: 

In a Binary Search Tree (BST), finding the Lowest Common Ancestor (LCA) involves traversing the tree from the root while comparing the values of the two nodes with the current node. At each step, if both nodes are smaller, move left; if larger, move right. When they diverge (one left, one right, or one is the current node), that node is the LCA.

This approach leverages the BST’s structure, efficiently narrowing down the search space based on node values.

Algorithm:

Step 1: Start at the root of the Binary Search Tree.

Step 2: Compare the values of the two nodes with the value of the current node.

  • If both nodes are smaller than the current node, they are both to its left hence move to its left child.
  • If both nodes are larger than the current node, they are both to its right hence move to its right child.
  • If one node is to the left and the other to the right of the current node, or if one node is the current node itself, then the current node is the LCA.

Step 3: Traverse down the tree based on the comparison of the node values, narrow done the search space by eliminating subtrees where the LCA cannot exist.

Step 4: Stop the recursion when both nodes are found in different subtrees of the current node or one of the nodes become the current node itself. Return the current node.

Code:

C++ Code

#include <iostream>
#include <climits>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
    // Value of the node
    int val;
    
    // Pointer to the left child node
    TreeNode* left;
    
    // Pointer to the right child node
    TreeNode* right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to find the lowest common ancestor (LCA)
    // of two nodes in a binary search tree (BST)
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Check if the root is null
        if (root == nullptr) {
            // If null, return null as there's no LCA
            return nullptr; 
        }
        
        // Store the value of the current root node
        int curr = root->val;
        
        // If both p and q values are greater
        // than the current root's value
        if (curr < p->val && curr < q->val) {
            // Recursively search in the
            // right subtree for the LCA
            return lowestCommonAncestor(root->right, p, q);
        }
        
        // If both p and q values are smaller
        // than the current root's value
        if (curr > p->val && curr > q->val) {
            // Recursively search in the
            // left subtree for the LCA
            return lowestCommonAncestor(root->left, p, q);
        }
        
        // If the values are on either side of the current root's value,
        // or one of the values matches the current root's value,
        // return the current root as the LCA
        return root;
    }
};


// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == nullptr) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root->left);

    // Print the value of the current node
    cout << root->val << " ";

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root->right);
}

int main() {
    Solution solution;

    // Creating a sample tree
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    cout << "Inorder Traversal of Tree:" << endl;
    printInOrder(root);
    cout << endl;

    // Node with value 2
    TreeNode* p = root->left->left;  
    
    // Node with value 4
    TreeNode* q = root->left->right; 
    
    TreeNode* lca = solution.lowestCommonAncestor(root, p, q);

    cout << "Lowest Common Ancestor of " << p->val << " and " << q->val << " is: " << lca->val << endl;

    return 0;
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

Lowest Common Ancestor of 2 and 4 is: 3

Time Complexity: O(H) where H is the height of the binary search tree as we are traversing along the height of the tree. In comparison to LCA in a binary tree where the time complexity is O(N), finding LCA in a binary search tree is more optimised.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal and algorithm.

Java Code

class TreeNode {
    // Value of the node
    int val;
    
    // Pointer to the left child node
    TreeNode left;
    
    // Pointer to the right child node
    TreeNode right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to find the lowest common ancestor (LCA)
    // of two nodes in a binary search tree (BST)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Check if the root is null
        if (root == null) {
            // If null, return null as there's no LCA
            return null; 
        }
        
        // Store the value of the current root node
        int curr = root.val;
        
        // If both p and q values are greater
        // than the current root's value
        if (curr < p.val && curr < q.val) {
            // Recursively search in the
            // right subtree for the LCA
            return lowestCommonAncestor(root.right, p, q);
        }
        
        // If both p and q values are smaller
        // than the current root's value
        if (curr > p.val && curr > q.val) {
            // Recursively search in the
            // left subtree for the LCA
            return lowestCommonAncestor(root.left, p, q);
        }
        
        // If the values are on either side of the current root's value,
        // or one of the values matches the current root's value,
        // return the current root as the LCA
        return root;
    }
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == null) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root.left);

    // Print the value of the current node
    System.out.print(root.val + " ");

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root.right);
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Creating a sample tree
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        System.out.println("Inorder Traversal of Tree:");
        printInOrder(root);
        System.out.println();

        // Node with value 2
        TreeNode p = root.left.left;  
    
        // Node with value 4
        TreeNode q = root.left.right; 
    
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);

        System.out.println("Lowest Common Ancestor of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

Lowest Common Ancestor of 2 and 4 is: 3

Time Complexity: O(H) where H is the height of the binary search tree as we are traversing along the height of the tree. In comparison to LCA in a binary tree where the time complexity is O(N), finding LCA in a binary search tree is more optimised.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal and algorithm.

Python Code

# Definition of TreeNode structure
# for a binary tree node
class TreeNode:
    # Constructor to initialize the node with a
    # value and set left and right pointers to null
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # Function to find the lowest common ancestor (LCA)
    # of two nodes in a binary search tree (BST)
    def lowestCommonAncestor(self, root, p, q):
        # Check if the root is None
        if root is None:
            # If None, return None as there's no LCA
            return None
        
        # Store the value of the current root node
        curr = root.val
        
        # If both p and q values are greater
        # than the current root's value
        if curr < p.val and curr < q.val:
            # Recursively search in the
            # right subtree for the LCA
            return self.lowestCommonAncestor(root.right, p, q)
        
        # If both p and q values are smaller
        # than the current root's value
        if curr > p.val and curr > q.val:
            # Recursively search in the
            # left subtree for the LCA
            return self.lowestCommonAncestor(root.left, p, q)
        
        # If the values are on either side of the current root's value,
        # or one of the values matches the current root's value,
        # return the current root as the LCA
        return root

# Function to perform an in-order traversal
# of a binary tree and print its nodes
def printInOrder(root):
    # Check if the current node
    # is None (base case for recursion)
    if root is None:
        # If None, return and
        # terminate the function
        return
    
    # Recursively call printInOrder
    # for the left subtree
    printInOrder(root.left)
    
    # Print the value of the current node
    print(root.val, end=" ")

    # Recursively call printInOrder
    # for the right subtree
    printInOrder(root.right)

if __name__ == "__main__":
    solution = Solution()

    # Creating a sample tree
    root = TreeNode(6)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    print("Inorder Traversal of Tree:")
    printInOrder(root)
    print()
    
    # Node with value 2
    p = root.left.left
    
    # Node with value 4
    q = root.left.right
    
    lca = solution.lowestCommonAncestor(root, p, q)
    print(f"Lowest Common Ancestor of {p.val} and {q.val} is: {lca.val if lca else None}")

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

Lowest Common Ancestor of 2 and 4 is: 3

Time Complexity: O(H) where H is the height of the binary search tree as we are traversing along the height of the tree. In comparison to LCA in a binary tree where the time complexity is O(N), finding LCA in a binary search tree is more optimised.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal and algorithm.

JavaScript Code

#include <iostream>
#include <climits>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
    // Value of the node
    int val;
    
    // Pointer to the left child node
    TreeNode* left;
    
    // Pointer to the right child node
    TreeNode* right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to find the lowest common ancestor (LCA)
    // of two nodes in a binary search tree (BST)
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Check if the root is null
        if (root == nullptr) {
            // If null, return null as there's no LCA
            return nullptr; 
        }
        
        // Store the value of the current root node
        int curr = root->val;
        
        // If both p and q values are greater
        // than the current root's value
        if (curr < p->val && curr < q->val) {
            // Recursively search in the
            // right subtree for the LCA
            return lowestCommonAncestor(root->right, p, q);
        }
        
        // If both p and q values are smaller
        // than the current root's value
        if (curr > p->val && curr > q->val) {
            // Recursively search in the
            // left subtree for the LCA
            return lowestCommonAncestor(root->left, p, q);
        }
        
        // If the values are on either side of the current root's value,
        // or one of the values matches the current root's value,
        // return the current root as the LCA
        return root;
    }
};


// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == nullptr) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root->left);

    // Print the value of the current node
    cout << root->val << " ";

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root->right);
}

int main() {
    Solution solution;

    // Creating a sample tree
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    cout << "Inorder Traversal of Tree:" << endl;
    printInOrder(root);
    cout << endl;

    // Node with value 2
    TreeNode* p = root->left->left;  
    
    // Node with value 4
    TreeNode* q = root->left->right; 
    
    TreeNode* lca = solution.lowestCommonAncestor(root, p, q);

    cout << "Lowest Common Ancestor of " << p->val << " and " << q->val << " is: " << lca->val << endl;

    return 0;
}

Output:

Inorder Traversal of Tree:

2 3 4 6 7 8

Lowest Common Ancestor of 2 and 4 is: 3

Time Complexity: O(H) where H is the height of the binary search tree as we are traversing along the height of the tree. In comparison to LCA in a binary tree where the time complexity is O(N), finding LCA in a binary search tree is more optimised.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal and algorithm.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article