# Lowest Common Ancestor in a Binary Search Tree.

Objective: Find the Lowest Common Ancestor of two given nodes in a Binary Search Tree

What is Lowest Common Ancestor

In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.

Similar Problem: Lowest Common Ancestor in a Binary Tree ( Not Binary Search Tree).

Example:

Input: A binary Search Tree and two nodes n1 and n2.

Appraoch:

1. Start will the root.
2. If root>n1 and root>n2 then lowest common ancestor will be in left subtree.
3. If root<n1 and root<n2 then lowest common ancestor will be in right subtree.
4. If Step 2 and Step 3 is false then we are at the root which is lowest common ancestor, return it.

Complete Code:

 public class LowestCommonAncestorBST { public Node LCA(Node root, Node n1, Node n2) { if (root == null) { return null; } // If root>n1 and root>n2 then lowest common ancestor will be in left // subtree. if (root.data > n1.data && root.data > n2.data) { return LCA(root.left, n1, n2); } // If rootn1 and root>n2 then lowest common ancestor will be in // left // subtree. if (root.data > n1.data && root.data > n2.data) { root = root.left; } // If root

Output:

```Recursive-Lowest Common Ancestor of Nodes 5 and 14 is : 10
Iterative-Lowest Common Ancestor of Nodes 5 and 14 is : 10
```

### 1 thought on “Lowest Common Ancestor in a Binary Search Tree.”

1. why (root.data <= n1.data) in the els if statement rather than (root.data < n1.data)