# 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():**

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

**getPath():**** **

- Let currentNode be root
- While currentNode is not null:
- Add the currentNode.data to the path
- If currentNode.data == nodeData then
- return path

- Else if nodeData < currentNode.data then
- currentNode = currentNode.left

- Else
- currentNode = currentNode.right

- 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():**

- Initialize Current Node as root
- While currentNode is not null:
- If nodeA < currentNode.data and nodeB < currentNode.data then
- currentNode = currentNode.left

- Else if nodeA > currentNode.data and nodeB > currentNode.data then
- currentNode = currentNode.right

- Else
- return currentNode.data

- If nodeA < currentNode.data and nodeB < currentNode.data then
- 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