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

- Start will the root.
- If root>n1 and root>n2 then lowest common ancestor will be in left subtree.
- If root<n1 and root<n2 then lowest common ancestor will be in right subtree.
- 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 root<n1 and root<n2 then lowest common ancestor will be in right | |

// subtree. | |

else if (root.data <= n1.data && root.data < n2.data) { | |

return LCA(root.right, n1, n2); | |

} | |

// if I am here that means i am at the root which is lowest common | |

// ancestor | |

return root; | |

} | |

public Node LCA2(Node root, Node n1, Node n2) { | |

while (root != 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) { | |

root = root.left; | |

} | |

// If root<n1 and root<n2 then lowest common ancestor will be in | |

// right | |

// subtree. | |

else if (root.data <= n1.data && root.data < n2.data) { | |

root = root.right; | |

} | |

// if I am here that means i am at the root which is lowest common | |

// ancestor | |

else { | |

return root; | |

} | |

} | |

return root; | |

} | |

public static void main(String[] args) throws java.lang.Exception { | |

Node root = new Node(15); | |

root.left = new Node(10); | |

root.right = new Node(20); | |

Node n1 = new Node(5); | |

root.left.left = n1; | |

root.left.right = new Node(13); | |

Node n2 = new Node(14); | |

root.left.right.right = n2; | |

root.left.right.left = new Node(12); | |

LowestCommonAncestorBST i = new LowestCommonAncestorBST(); | |

System.out.println("Recursive-Lowest Common Ancestor of Nodes " | |

+ n1.data + " and " + n2.data + " is : " | |

+ i.LCA(root, n1, n2).data); | |

Node x = i.LCA2(root, n1, n2); | |

System.out.println("Iterative-Lowest Common Ancestor of Nodes " | |

+ n1.data + " and " + n2.data + " is : " + x.data); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

left = null; | |

right = null; | |

} | |

} |

**Output**:

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

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