Thursday, May 5, 2022

Question 64 : How to find lowest common ancestor(LCA) in binary tree.

 You need to write a program to find LCA in binary tree.




Recursive Algorithm (For nodes A and B):

  • If node is null, return it
  • If we find A or B, return it.
  • Traverse left subtree and right subtree.
  •  If we get both left and right for any node as not null, it will be the lowest common ancestor of two given nodes.
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
        if(root == null)
            return null;
        if(root.data == a.data || root.data == b.data )
            return root;
 
        TreeNode left=lowestCommonAncestor(root.left,a,b);
        TreeNode right=lowestCommonAncestor(root.right,a,b);
 
        // If we get left and right not null , it is lca for a and b
        if(left!=null && right!=null)
            return root;
        if(left== null)
            return right;
        else
            return left;
 
    }

Complete java program:

public class BinaryTreeLCA {
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
        if(root == null)
            return null;
        if(root.data == a.data || root.data == b.data )
            return root;
 
        TreeNode left=lowestCommonAncestor(root.left,a,b);
        TreeNode right=lowestCommonAncestor(root.right,a,b);
 
        // If we get left and right not null , it is lca for a and b
        if(left!=null && right!=null)
            return root;
        if(left== null)
            return right;
        else
            return left;
 
    }
    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Lowest common ancestor for node 5 and 30:");
        TreeNode node5=new TreeNode(5);
        TreeNode node30=new TreeNode(30);
        System.out.println(lowestCommonAncestor(rootNode,node5,node30).data);
 
    }
 
    public static TreeNode createBinaryTree()
    {
 
        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
        TreeNode node5=new TreeNode(5);
        TreeNode node45=new TreeNode(45);
        TreeNode node55=new TreeNode(55);
 
        rootNode.left=node20;
        rootNode.right=node60;
 
        node20.left=node10;
        node20.right=node30;
 
        node60.left=node50;
        node60.right=node70;
 
        node10.left=node5;
        node50.right=node55;
        return rootNode;
    }
}

When you run above program, you will get below output:
Lowest common ancestor for node 5 and 30:
20
 


You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS