# Lowest Common Ancestor in Binary Search Tree  Difficulty Level Easy
Binary Search Tree Binary Tree Traversal Tree Tree Traversal

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   ## 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.

Advantages of BST over Hash Table

## 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 