fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12.         // create some input
  13.         Node root = new Node(1);
  14.         Node two = new Node(2);
  15.         Node three = new Node(3);
  16.         Node four = new Node(4);
  17.         Node five = new Node(5);
  18.  
  19.         root.left = two;
  20.         root.right = three;
  21.         three.left = four;
  22.         three.right = five;
  23.  
  24.         Node lcaNode = leastCommonAncestor(root, four, five);
  25.         System.out.println("LCA :" + lcaNode.value);
  26.         Node lcaNode2 = leastCommonAncestor(root, three, five);
  27.         System.out.println("LCA :" + lcaNode2.value);
  28. 	}
  29.  
  30. 	public static Node leastCommonAncestor(Node root, Node one, Node two)
  31. 	{
  32. 		if( one == null ) return two;
  33. 		if( two == null ) return one;
  34.  
  35. 		Stack<Node> s1 = new Stack<Node>();
  36. 		Stack<Node> s2 = new Stack<Node>();
  37.  
  38. 		s1.push(root);
  39. 		s2.push(root);
  40.  
  41. 		boolean oneFound = findPath(root, one, s1);
  42. 		boolean twoFound = findPath(root, two, s2);
  43.  
  44. 		if( ! oneFound || ! twoFound ) return null;
  45.  
  46. 		Stack rev1 = reverseStack(s1);
  47. 		Stack rev2 = reverseStack(s2);
  48.  
  49. 		Node first = (Node) rev1.pop();
  50. 		Node second = (Node) rev2.pop();
  51. 		Node lca = first;
  52.  
  53. 		while( first.value == second.value )
  54. 		{
  55. 			lca = first;
  56. 			if( ! rev1.empty() ) 
  57. 			{
  58. 				first = (Node) rev1.pop();	
  59. 			}
  60.  
  61. 			if( ! rev2.empty() )
  62. 			{
  63. 				second = (Node) rev2.pop();	
  64. 			}
  65. 		}
  66.  
  67. 		return lca;
  68. 	}
  69.  
  70. 	public static Stack reverseStack(Stack s)
  71. 	{
  72. 		if( s == null ) return null;
  73.  
  74. 		Stack rev = new Stack();
  75.  
  76. 		while( ! s.empty() ) 
  77. 		{
  78. 			rev.push( (Node) s.pop() );
  79. 		}	
  80.  
  81. 		return rev;
  82. 	}
  83.  
  84. 	public static boolean findPath(Node current, Node destNode, Stack s)
  85. 	{
  86. 		if( current == null ) return false;
  87.  
  88. 		if( current.value == destNode.value )
  89. 		{
  90. 			return true;
  91. 		}
  92.  
  93. 		if( current.left != null )
  94. 		{
  95. 			s.push(current.left);
  96. 			boolean found = findPath(current.left, destNode, s);
  97.  
  98. 			if(  found ) return true;
  99. 			else s.pop();
  100. 		}
  101.  
  102. 		if( current.right != null )
  103. 		{
  104. 			s.push(current.right);
  105. 			boolean found = findPath(current.right, destNode, s);
  106.  
  107. 			if(  found ) return true;
  108. 			else s.pop();
  109. 		}
  110.  
  111. 		return false;
  112. 	}
  113. }
  114.  
  115. class Node
  116. {
  117.     public Node left=null;
  118.     public int value;
  119.     public boolean visited=false;
  120.     public Node right=null;
  121.  
  122.     public Node(int value)
  123.     {
  124.         this.value = value;
  125.     }
  126. }
Success #stdin #stdout 0.1s 320256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
LCA :3
LCA :3
https://ideone.com/qHaUuo
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!