Lowest Common Ancestor in a Binary Tree & Binary Search Tree.

       

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.regex.*;



class Node

{

    int data;

    Node left, right;



    Node(int item)

    {

        data = item;

        left = right = null;

    }

}



class BinaryTree

{

    Node root;

 

    /* Function to find LCA of n1 and n2. if tree is BST*/

    Node lca(Node node, int n1, int n2)

    {

        if (node == null)

            return null;



        if (node.data > n1 && node.data > n2)

            return lca(node.left, n1, n2);



        if (node.data < n1 && node.data < n2)

            return lca(node.right, n1, n2);



        return node;

    }

    /* Function to find LCA of n1 and n2. if tree is Binary Tree*/

    Node fun(Node head1,int val1, int val2) {

            if(head1==null)

                return null;

        if(head1.data==val1 || head1.data==val2)

            return head1;

        Node left = fun(head1.left,val1,val2);

        Node right = fun(head1.right,val1,val2);



        if(left!=null && left.data==val1 && right!=null && right.data==val2)

            return head1;

        if(left!=null && left.data==val2 &&  right!=null && right.data==val1)

            return head1;

        if(left!=null)

            return left;

        if(right!=null)

            return right;

        return null;

    }

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);



        int n1 = 10, n2 = 14;

        Node t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);



        n1 = 14;

        n2 = 8;

        t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);



        n1 = 14;

        n2 = 20;

        // t = tree.lca(tree.root, n1, n2);

        t = tree.fun(tree.root,n1,n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

     

    }

}