Lowest Common Ancestor (LCA) of binary search tree in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

In this post, we will see how to find lowest common ancestor(LCA) of two nodes in binary search tree.
We have already seen how to find LCA in binary tree. It is much simple than that.
Lets understand with example.

As you can see here, LCA is nothing but lowest common parent of two nodes.

Recursive Algorithm (For nodes A and B):

  • If node is null, return it
  • If node is greater than A and B, traverse left subtree
  • If node is lesser than A and B , traverse right subtree.
  • If above both condition do not satisfy, then node is LCA of A and B

Iterative solution:

It is similar to recursive solution, here we are using while loop to traverse nodes.

Complete java program:

When you run above program, you will get below output:
Please go through java interview programs for more such programs.


You may also like:

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.