How to find lowest common ancestor in binary tree in Java

In this tutorial, we will see how to find the lowest common ancestor(LCA) in a binary tree in Java. It is nothing but the lowest common parent of any two given nodes. We will be solving our problem using recursion.

Following given is the algorithm which we will use in the program:

  • For the base condition, we will check if the node is null and return it.
  • If we find node data equal to any of the given nodes, we return it.
  • We will traverse left subtree and right subtree.
  • ¬†If we get both left and right for any node as not null, it will be our lowest common ancestor of two given nodes.

Below given is the implementation of this algorithm:

 




public static Node LCA_of_nodes(Node root, Node a, Node b) {
    if(root == null)
      return null;
    if(root.data == a.data || root.data == b.data )
      return root;
 
    Node left=LCA(root.left,a,b);
    Node right=LCA(root.right,a,b);

    if(left!=null && right!=null)
      return root;
    if(left== null)
      return right;
    else
      return left;
  }

We will use this method in our java program to find out the lowest common ancestor/common parent of the two nodes.

Also read:

Java Code: find lowest common ancestor in binary tree

public class Main {
  public static class Node
  {
    int data;
    Node left;
    Node right;
      Node(int data)
    {
      this.data=data;
    }
  }
 
  public static Node LCA_of_nodes(Node root, Node a, Node b) {
    if(root == null)
      return null;
    if(root.data == a.data || root.data == b.data )
      return root;
 
    Node left=LCA_of_nodes(root.left,a,b);
    Node right=LCA_of_nodes(root.right,a,b);
 
    if(left!=null && right!=null)
      return root;
    if(left== null)
      return right;
    else
      return left;
 
  }
  public static void main(String[] args)
  {
    Node root=createBinaryTree();
    System.out.println("LCA for node 5 and 25:");
    Node node5=new Node(5);
    Node node25=new Node(25);
    System.out.println(LCA_of_nodes(root,node5,node25).data);
 
  }
 
  public static Node createBinaryTree()
  {
 
    Node root =new Node(40);
    Node node20=new Node(20);
    Node node10=new Node(10);
    Node node25=new Node(25);
    Node node60=new Node(60);
    Node node50=new Node(50);
    Node node70=new Node(70);
    Node node5=new Node(5);
    Node node45=new Node(45);
    Node node55=new Node(55);
 
    root.left=node20;
    root.right=node60;
 
    node20.left=node10;
    node20.right=node25;
 
    node60.left=node50;
    node60.right=node70;
 
    node10.left=node5;
    node50.right=node55;
    return root;
  }
}

 

Output:

LCA for node 5 and 25:
20

Also, read these:


Leave a Reply

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