fork download
copy 
  1. class TreeNode {
  2. int numKey;
  3. char charKey;
  4. public TreeNode left, right;
  5.  
  6.  
  7. TreeNode(int keyVal){
  8. 	numKey=keyVal;
  9. }
  10.  
  11. TreeNode(char keyVal){
  12. 	charKey=keyVal;
  13. }
  14.  
  15. TreeNode(char keyVal,TreeNode leftChild, TreeNode rightChild){
  16. 	charKey=keyVal;
  17. 	left=leftChild;
  18. 	right=rightChild;
  19. }
  20.  
  21. public static TreeNode findLCA(TreeNode root, int val1, int val2){
  22. 	LCA lcaObj = new LCA();
  23. 	lcaObj.val1=val1;
  24. 	lcaObj.val2=val2;
  25. 	return findLCA_internal(root,lcaObj);
  26.  
  27. }
  28.  
  29. private static TreeNode findLCA_internal(TreeNode root,LCA lcaObj ){
  30. 	if(root==null) return null;
  31.  
  32. 	if(lcaObj.val1Found && lcaObj.val2Found){
  33. 		// both values are found at previous level so do nothing more
  34. 		return null;
  35. 	}else{
  36. 		boolean val1FlagBefore = lcaObj.val1Found;
  37. 		boolean val2FlagBefore = lcaObj.val2Found;
  38.  
  39. 		if(!lcaObj.val1Found && root.numKey==lcaObj.val1){
  40. 			lcaObj.val1Found=true;
  41. 		}if(!lcaObj.val2Found && root.numKey==lcaObj.val2){
  42. 			lcaObj.val2Found=true;
  43. 		}
  44. 		TreeNode lcaPresentInLeftTree = findLCA_internal(root.left,lcaObj);
  45. 		if(lcaPresentInLeftTree !=null){
  46. 			return lcaPresentInLeftTree;
  47. 		}else{
  48. 			TreeNode lcaPresentInRightTree  = findLCA_internal(root.right,lcaObj);
  49. 			if(lcaPresentInRightTree!=null) {
  50. 				return lcaPresentInRightTree;
  51. 			}else{
  52. 				// LCA is not presnt in left tree nor it is present in right tree. So check if this node itself if LCA
  53. 				//  before this node was checked ;val1 flag was false and afterwards it is true. 
  54. 				// ALSO 
  55. 				// before this node was checked; val2 flag was false and and afterwards it is true.
  56. 				// This root is the LCA
  57. 				if(!val1FlagBefore && lcaObj.val1Found && !val2FlagBefore && lcaObj.val2Found){
  58. 					return root;
  59. 				}else{
  60. 					// So either or both of keys are not present in this tree
  61. 					return null;
  62. 				}
  63.  
  64. 			}
  65. 		}
  66.  
  67. 	}
  68. }
  69.  
  70. public static void main(String[] args) {
  71. 	/*
  72. 	 10
  73. 	/ \
  74.    20  30
  75.    / \
  76.   40 50
  77.   */
  78. 	TreeNode root = new TreeNode(10);
  79. 	root.left= new TreeNode(20);
  80. 	root.left.left= new TreeNode(40);
  81. 	root.left.right= new TreeNode(50);
  82. 	root.right= new TreeNode(30);
  83.  
  84. 	TreeNode lcaNode = null;
  85. 	lcaNode = findLCA(root, 50, 40);
  86. 	System.out.println("findLCA(root, 50, 40)" + lcaNode.numKey );
  87. 	lcaNode = findLCA(root, 30, 40);
  88. 	System.out.println("findLCA(root, 30, 40)"+ lcaNode.numKey );
  89. 	lcaNode = findLCA(root, 30, 20);
  90. 	System.out.println("findLCA(root, 30, 20)"+ lcaNode.numKey );
  91. 	lcaNode = findLCA(root, 50, 20);
  92. 	System.out.println("findLCA(root, 50, 20)"+ lcaNode.numKey );
  93.  
  94. }
  95.  
  96. }
  97.  
  98.  
  99. class LCA{
  100. 	int val1,val2;
  101. 	boolean val1Found=false;
  102. 	boolean val2Found=false;
  103.  
  104. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
findLCA(root, 50, 40)20
findLCA(root, 30, 40)10
findLCA(root, 30, 20)10
findLCA(root, 50, 20)20
https://ideone.com/McU0wN
language:
Java (HotSpot 12)
created:
11 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!