Lowest Common Ancestor in Binary Search Tree

Difficulty Level Easy
Frequently asked in Amazon Facebook LinkedIn Oracle
Binary Search Tree Binary Tree Traversal Tree Tree TraversalViews 2007

Given the root of a binary search tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes in a given binary search tree.

Example

Lowest Common Ancestor in Binary Search Tree

Naive Approach for Lowest Common Ancestor in Binary Search Tree

Find the LCA(n1, n2) using the optimal approach to find LCA in the Binary tree, as BST is also a binary tree.

If we assume that n1 and n2, for which we have to find LCA, exists in the tree, then the above problem can be solved in a single traversal.

Traverse the tree, for every node we have one of the four cases,

  1. The current node is either n1 or n2, in this case, we return the node.
  2. One of the subtrees of the current node contains n1 and the other contains n2, this node is the LCA, return the node.
  3. One subtree of the current node contains both n1 and n2, we return what the subtree returns.
  4. None of the subtrees contains n1 and n2, return null.

Time Complexity = O(n), with single traversal 
where n is the number of nodes in the tree.

Optimal Approach for Lowest Common Ancestor in Binary Search Tree

Using the properties of BST, the LCA can be found in much lesser time complexity.

  1. Traverse the BST starting from the root (Initialize curr as root).
  2. If the current node’s value lies between n1 and n2(both inclusive), then this is the LCA.
  3. Else if node’s value is less than both n1 and n2, LCA is present in the right half (curr becomes curr.right).
  4. Else LCA is present in the left half (curr becomes curr.left).

Explanation

Consider the BST in the above image, lets find the LCA(32, 40)

Start traversing the tree starting from the root.

  • Current node’s value = 20
    20 < 32 and 20 < 40, LCA is present in right sub tree
  • Current node’s value = 24
    24 < 32 and 20 < 40, LCA is present in right sub tre
  • Current node’s value = 35
    35 >= 32 and 35 <= 40, so this is the LCA
    That is, LCA(32, 40) = 35

JAVA Code for Lowest Common Ancestor in Binary Search Tree

public class LCABST {
    // Class to represent a node in BST
    static class Node {
        int data;
        Node left, right;

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

    // Function to return LCA of two nodes, and return -1 if LCA does not exist
    private static int LCA(Node root, int n1, int n2) {
        // No LCA for an empty tree
        if (root == null) {
            return -1;
        }

        // Traverse the tree starting from root
        Node curr = root;
        int lca = -1;
        while (curr != null) {
            if (curr.data < n1 && curr.data < n2) {
                // LCA is present in the right sub tree
                curr = curr.right;
            } else if (curr.data > n1 && curr.data > n2) {
                // LCA is present in left sub tree
                curr = curr.left;
            } else {
                lca = curr.data;
                break;
            }
        }

        // Return LCA
        return lca;
    }

    public static void main(String[] args) {
        // Constructing the BST in above example
        Node root = new Node(20);
        root.left = new Node(11);
        root.right = new Node(24);
        root.right.left = new Node(21);
        root.right.right = new Node(35);
        root.right.right.left = new Node(32);
        root.right.right.right = new Node(40);

        // Queries
        System.out.println(LCA(root, 24, 40));
        System.out.println(LCA(root, 11, 21));
        System.out.println(LCA(root, 32, 40));
    }
}

C++ Code for Lowest Common Ancestor in Binary Search Tree

#include <iostream>
using namespace std;

// Class representing node of binary search tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

// Function to return LCA of two nodes, and return -1 if LCA does not exist
int LCA(Node *root, int n1, int n2) {
    // No LCA for an empty tree
    if (root == NULL) {
        return -1;
    }
    
    // Traverse the tree starting from root
    Node *curr = root;
    int lca = -1;
    while (curr != NULL) {
        if (curr->data < n1 && curr->data < n2) {
            // LCA is present in the right sub tree
            curr = curr->right;
        } else if (curr->data > n1 && curr->data > n2) {
            // LCA is present in left sub tree
            curr = curr->left;
        } else {
            lca = curr->data;
            break;
        }
    }
    
    // Return LCA
    return lca;
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(20);
    root->left = newNode(11);
    root->right = newNode(24);
    root->right->left = newNode(21);
    root->right->right = newNode(35);
    root->right->right->left = newNode(32);
    root->right->right->right = newNode(40);
    
    // Queries
    cout<<LCA(root, 24, 40)<<endl;
    cout<<LCA(root, 11, 21)<<endl;
    cout<<LCA(root, 32, 40)<<endl;
    
    return 0;
}
24
20
35

Complexity Analysis

Time Complexity = O(h), where h is the height of BST

References

Translate »