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.  
  8. class TreeTraversal {
  9.  
  10. 	public static final List<Node> inOrderList = new ArrayList<>(); 
  11. 	public static final List<Node> preOrderList = new ArrayList<>();
  12. 	public static final List<Node> postOrderList = new ArrayList<>(); 
  13.  
  14. 	public static void main(String[] args) {
  15.  
  16. 		Node n1 = new Node(1);
  17. 		Node n2 = new Node(2);
  18. 		Node n3 = new Node(3);
  19. 		Node n4 = new Node(4);
  20. 		Node n5 = new Node(5);
  21. 		Node n6 = new Node(6);
  22. 		Node n7 = new Node(7);
  23. 		Node n8 = new Node(8);
  24. 		Node n9 = new Node(9);
  25. 		Node n10 = new Node(10);
  26. 		Node n11 = new Node(11);
  27. 		Node n12 = new Node(12);
  28. 		Node n13 = new Node(13);
  29.  
  30. 		n1.left = n2;
  31. 		n1.right = n3;
  32.  
  33. 		n2.left = n4;
  34. 		n2.right = n5;
  35.  
  36. 		n3.left = n6;
  37. 		n3.right = n7;
  38.  
  39. 		n4.left = n4.right = null;
  40.  
  41. 		n5.left = n10;
  42. 		n5.right = n11;
  43.  
  44. 		n6.left = n6.right = null;
  45.  
  46. 		n7.left = n8;
  47. 		n7.right = n9;
  48.  
  49. 		n10.left = n12;
  50. 		n10.right = n13;
  51.  
  52. 		n11.left = n11.right = null;
  53.  
  54. 		n8.left = n8.right = null;
  55. 		n9.left = n9.right = null;
  56.  
  57.  
  58. 		inOrder(n1);
  59. 		System.out.println("Inorder traversal is " + inOrderList);
  60. 		postOrder(n1);
  61. 		System.out.println("Postorder traversal is " + postOrderList);
  62.  
  63. 		/*
  64. 		 * 1. we take the list of nodes that are in between them
  65. 		 * 2. then we take the address of each node of the above found list 
  66. 		 * 3. the node that is in the farthest position, will be the LCA 
  67. 		 */
  68. 		Node fn = n6;
  69. 		Node sn = n9;
  70. 		System.out.println("We are gonna find the LCA between " + fn + " & " + sn);
  71. 		List<Node> inBetweenList = inBetween(inOrderList, fn, sn);
  72. 		System.out.println("The nodes in between " + fn + " and " + sn + " are as follows " + inBetweenList);
  73. 		System.out.println("LCA of " + fn + " & " + sn + " is " + lca(inBetweenList, postOrderList));
  74. 	}
  75.  
  76. 	public static List<Node> inBetween(List<Node> inOrder, Node fn, Node sn){
  77. 		int i1 = inOrder.indexOf(fn);
  78. 		int i2 = inOrder.indexOf(sn);
  79. 		List<Node> result = i1 > i2 ? inOrder.subList(i2, i1 + 1) :  inOrder.subList(i1, i2 + 1);
  80. 		return result;
  81. 	}
  82.  
  83. 	public static Node lca(List<Node> inBetweenList, List<Node> postOrderList){
  84. 		Node result = null;
  85. 		int maxIndex = 0;
  86. 		for(Node node : inBetweenList){
  87. 			maxIndex = postOrderList.indexOf(node) > maxIndex ? postOrderList.indexOf(node) : maxIndex;
  88. 		}
  89.  
  90. 		result = postOrderList.get(maxIndex);
  91. 		return result;
  92. 	}
  93.  
  94. 	public static void inOrder(Node root){
  95. 		if(root == null){
  96. 			return;
  97. 		}
  98. 		inOrder(root.left);
  99. 		inOrderList.add(root);
  100. 		inOrder(root.right);
  101. 	}
  102.  
  103. 	public static void preOrder(Node root){
  104. 		if(root == null){
  105. 			return;
  106. 		}
  107. 		preOrderList.add(root);
  108. 		preOrder(root.left);
  109. 		preOrder(root.right);
  110.  
  111. 	}
  112.  
  113. 	public static void postOrder(Node root){
  114. 		if(root == null){
  115. 			return;
  116. 		}
  117. 		postOrder(root.left);
  118. 		postOrder(root.right);
  119. 		postOrderList.add(root);
  120. 	}
  121.  
  122. }
  123.  
  124.  
  125. class Node{
  126. 	public Node left;
  127. 	public Node right;
  128. 	public int info;
  129.  
  130. 	public Node(int info){
  131. 		this.info = info;
  132. 		this.left = null;
  133. 		this.left = null;
  134. 	}
  135.  
  136. 	public String toString(){
  137. 		return "" + this.info;
  138. 	}
  139. }
Success #stdin #stdout 0.11s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal is [4, 2, 12, 10, 13, 5, 11, 1, 6, 3, 8, 7, 9]
Postorder traversal is [4, 12, 13, 10, 11, 5, 2, 6, 8, 9, 7, 3, 1]
We are gonna find the LCA between 6 & 9
The nodes in between 6 and 9 are as follows [6, 3, 8, 7, 9]
LCA of 6 & 9 is 3
https://ideone.com/V4n48d
LCA
language:
Java (HotSpot 12)
created:
8 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!