LowestCommonAncesstor

public class LowestCommonAncesstor {
   
    public static void main(String[] args) {
        int[] arr = {3,6,5,9,2,8};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = getLCA(root, 5, 8);//output 6
         System.out.println(node.value);
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    static Node getLCA(Node currentNode,int A,int B) {
        if(currentNode==null) {
            return null;
        }
        if(currentNode.value==A || currentNode.value==B) {
            return currentNode;
        }
        Node left = getLCA(currentNode.left, A, B);
        Node right = getLCA(currentNode.right, A, B);
        if(null!=left && null!=right) {
            return currentNode;
        }
        if(null==left) {
            return right;
        }else {
            return left;
        }
    }
   
}