Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

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:

Lowest-Common-Ancestor-BST

Lowest-Common-Ancestor-BST

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.
LCA-in-Binary-Search-Tree

LCA-in-Binary-Search-Tree

Complete Code:


Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: