Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    **i got this answer from the youtube **

    JAVA EASY Youtbe Solution

    import java.io.; import java.util.*;

    public class Solution {

    public static class Node
    {
        public int data ;
        public Node leftNode;
        public Node rightNode;
        public Node(int data)
        {
            this.data = data;
            this.leftNode = null;
            this.rightNode = null;
    
        }
    }
    
    
    public static Node buildTree(Node root,int data)
    {
        if(root == null)
        {
            root = new Node(data);
            return root;
        }
    
        if(root.data > data)
        {
            root.leftNode = buildTree(root.leftNode, data);
        }
        if(root.data<data)
        {
            root.rightNode = buildTree(root.rightNode, data);
        }
        return root;
    }
    
    public static Node lca(Node root,int a,int b)
    {
        if(root.data < a && root.data < b)
        {
            return lca(root.rightNode,a,b);
        }
        if(root.data > a && root.data > b)
        {
            return lca(root.leftNode,a,b);
        }
        return root;
    }
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc=  new Scanner(System.in);
            Node root = null;
            int n = sc.nextInt();
            int i=0;
            while(i<n)
            {
                i++;
                int inp = sc.nextInt();
                root = buildTree(root, inp);
            }
            int a,b;
            a=sc.nextInt();b=sc.nextInt();
            Node lcaNode = lca(root, a, b);
            System.out.println(lcaNode.data);
            sc.close();
    
    
    }
    

    }