Find the lowest common ancestor of a node in a binary search tree

The lowest common ancestor is defined between two nodes nodeA and nodeB as the lowest node in a Tree that has both nodeA and nodeB as descendants (where we allow a node to be a descendant of itself).

The General Idea to find the lowest common ancestor is to find the path from the root to the nodes and then return to the last node which is common in the path.

Diagram:

For example:

In the given figure find the lowest common ancestor of nodes 1 and 3 

For first find the paths from the root to 1 and 3

Path 4 to 1: 4->2->1

Path 4 to 3: 4->2->3

So the last common node is 2, therefore 2 is the lowest common ancestor

Algorithm:

getLowestCommonAncestor():

1. Get the pathA and pathB by traversing the BST 
2. Check if any of the path lengths is 0, if yes return -1 denoting that no common ancestor is present
3. Return the last common node in the path

getPath():

1. Let currentNode be root
2. While currentNode is not null:
   1. Add the currentNode.data to the path
   2. If currentNode.data == nodeData then 
      1. return path
   3. Else if nodeData < currentNode.data then 
      1. currentNode = currentNode.left
   4. Else 
      1. currentNode = currentNode.right
3. Return empty array, it denotes we have not found the node in the above steps, and the node is not present in the BST

Complexity:

Complexity of getLowestCommonAncestor:

Time Complexity: O(Height of Binary Search Tree) 

Space Complexity: O(Height of Binary Search Tree)

The Time Complexity of the given problem is O(LogN) as we are finding the paths from the root to the node which takes O(Height of Binary Search Tree) and as we are storing the path in an array the Space Complexity is also O(Height of Binary Search Tree)

We can Further Optimize the Algorithm by not storing the paths and directly traversing the tree till the node is same!!

Algorithm:

getLowestCommonAncestor():

1. Initialize Current Node as root
2. While currentNode is not null:
   1. If nodeA < currentNode.data and nodeB < currentNode.data then
      1. currentNode = currentNode.left
   2. Else if nodeA > currentNode.data and nodeB > currentNode.data then
      1. currentNode = currentNode.right
   3. Else 
      1. return currentNode.data
3. return -1

Complexity of getLowestCommonAncestorOptimally:

Time Complexity: O(Height of Binary Search Tree) 

Space Complexity: O(1)

The Time Complexity of the given problem is the same as the algorithm we have discussed before, but the Space Complexity is Constant i.e O(1) as we are not storing the path.

Java Code:

import java.util.ArrayList;


class BinarySearchTree {
   // Node class for Binary Search Tree
   class Node {
       int data;
       Node left, right;

       // Constructor to set the value of the node
       Node(int data) {
           this.data = data;
           this.left = null;
           this.right = null;
       }
   }

   private Node root = null;

   // Insert a value in BST Recursively
   public void insert(int dataToAdd) {
       // Calling the callback function and passing root as parameter
       root = insertCallback(dataToAdd, root);
   }

   private Node insertCallback(int dataToAdd, Node node) {
       // If node is null then create the node with the dataToAdd and return it
       if (node == null) {
           return new Node(dataToAdd);
       }


       // Go to left or right depending on the dataToAdd value
       if (dataToAdd < node.data) {
           // The node from the insertCallback will be assigned to the left of node
           node.left = insertCallback(dataToAdd, node.left);
       } else {
           // The node from the insertCallback will be assigned to the right of node
           node.right = insertCallback(dataToAdd, node.right);
       }


       // Return the current node
       return node;
   }


   // Function which returns ArrayList of the path from root to the node
   public ArrayList<Integer> getPath(int nodeData){
       // Variable to store the path from root to the node
       ArrayList<Integer> path = new ArrayList<>();
      
       Node currentNode = root;
       while(currentNode != null){
           path.add(currentNode.data);


           if(currentNode.data == nodeData){
               // Return the path when the nodeData matches with the currentNode data
               return path;
           }else if(nodeData < currentNode.data){
               // Move currentNode to the left
               currentNode = currentNode.left;
           }else{
               // Move currentNode to the right
               currentNode = currentNode.right;
           }
       }


       // Return an empty ArrayList if the node was not found
       return new ArrayList<Integer>();
   }


   // Function to find the common ancestor of nodeA and nodeB
   public int getLowestCommonAncestor(int nodeA, int nodeB){
       ArrayList<Integer> pathA = getPath(nodeA);
       ArrayList<Integer> pathB = getPath(nodeB);
      
       // If nodeA or nodeB is not present in the tree then return -1
       if(pathA.size() == 0 || pathB.size() == 0) return -1;


       // We start at the 0th index and increment till pathA and pathB has same values
       int i = 0;
       while(i < pathA.size() && i < pathB.size() && pathA.get(i) == pathB.get(i)){
           i++;
       }


       // So the index before i will be the last common node in the tree
       return pathA.get(i - 1);       
   }


   // Function to find the common ancestor of nodeA and nodeB optimally
   public int getLowestCommonAncestorOptimally(int nodeA, int nodeB){
       Node currentNode = root;


       while(currentNode != null){
           if(nodeA < currentNode.data && nodeB < currentNode.data){
               // If both the nodes are in the left then go to left
               currentNode = currentNode.left;
           }else if(nodeA > currentNode.data && nodeB > currentNode.data){
               // If both the nodes are in the right then go to right
               currentNode = currentNode.right;
           }else{
               // For all other cases we return the currentNode.Data,
               // as this node will be the junction from which the two paths separate
               return currentNode.data;
           }
       }


       return -1;
   }


   public static void main(String[] args) {
       // Inserting the values in the BST
       BinarySearchTree bst = new BinarySearchTree();
       bst.insert(4);
       bst.insert(7);
       bst.insert(2);
       bst.insert(1);
       bst.insert(3);


       // Printing the lowest common ancestor of two nodes
       System.out.println("Result using getLowestCommonAncestor(): ");
       System.out.println("The Lowest Common Ancestor of 1 and 3: " + 
           bst.getLowestCommonAncestor(1, 3));
       System.out.println("The Lowest Common Ancestor of 1 and 7: " + 
           bst.getLowestCommonAncestor(1, 7));
       System.out.println("The Lowest Common Ancestor of 3 and 7: " + 
           bst.getLowestCommonAncestor(3, 7));


       System.out.println("\nResult using getLowestCommonAncestorOptimally(): ");
       System.out.println("The Lowest Common Ancestor of 1 and 3: " + 
           bst.getLowestCommonAncestorOptimally(1, 3));
       System.out.println("The Lowest Common Ancestor of 1 and 7: " + 
           bst.getLowestCommonAncestorOptimally(1, 7));
       System.out.println("The Lowest Common Ancestor of 3 and 7: " + 
           bst.getLowestCommonAncestorOptimally(3, 7));
   }


}

Output:

Result using getLowestCommonAncestor(): 

The Lowest Common Ancestor of 1 and 3: 2

The Lowest Common Ancestor of 1 and 7: 4

The Lowest Common Ancestor of 3 and 7: 4

Result using getLowestCommonAncestorOptimally(): 

The Lowest Common Ancestor of 1 and 3: 2

The Lowest Common Ancestor of 1 and 7: 4

The Lowest Common Ancestor of 3 and 7: 4