/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
        // create some input
        Node root = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        
        root.left = two;
        root.right = three;
        three.left = four;
        three.right = five;
        
        Node lcaNode = leastCommonAncestor(root, four, five);
        System.out.println("LCA :" + lcaNode.value);
        Node lcaNode2 = leastCommonAncestor(root, three, five);
        System.out.println("LCA :" + lcaNode2.value);
	}
	
	public static Node leastCommonAncestor(Node root, Node one, Node two)
	{
		if( one == null ) return two;
		if( two == null ) return one;

		Stack<Node> s1 = new Stack<Node>();
		Stack<Node> s2 = new Stack<Node>();
		
		s1.push(root);
		s2.push(root);
		
		boolean oneFound = findPath(root, one, s1);
		boolean twoFound = findPath(root, two, s2);
		
		if( ! oneFound || ! twoFound ) return null;
		
		Stack rev1 = reverseStack(s1);
		Stack rev2 = reverseStack(s2);
		
		Node first = (Node) rev1.pop();
		Node second = (Node) rev2.pop();
		Node lca = first;
		
		while( first.value == second.value )
		{
			lca = first;
			if( ! rev1.empty() ) 
			{
				first = (Node) rev1.pop();	
			}
			
			if( ! rev2.empty() )
			{
				second = (Node) rev2.pop();	
			}
		}
		
		return lca;
	}
	
	public static Stack reverseStack(Stack s)
	{
		if( s == null ) return null;
		
		Stack rev = new Stack();
		
		while( ! s.empty() ) 
		{
			rev.push( (Node) s.pop() );
		}	
		
		return rev;
	}
	
	public static boolean findPath(Node current, Node destNode, Stack s)
	{
		if( current == null ) return false;
		
		if( current.value == destNode.value )
		{
			return true;
		}
		
		if( current.left != null )
		{
			s.push(current.left);
			boolean found = findPath(current.left, destNode, s);
			
			if(  found ) return true;
			else s.pop();
		}

		if( current.right != null )
		{
			s.push(current.right);
			boolean found = findPath(current.right, destNode, s);
			
			if(  found ) return true;
			else s.pop();
		}
		
		return false;
	}
}

class Node
{
    public Node left=null;
    public int value;
    public boolean visited=false;
    public Node right=null;
   
    public Node(int value)
    {
        this.value = value;
    }
}