/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; class TreeTraversal { public static final List<Node> inOrderList = new ArrayList<>(); public static final List<Node> preOrderList = new ArrayList<>(); public static final List<Node> postOrderList = new ArrayList<>(); Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); Node n4 = new Node(4); Node n5 = new Node(5); Node n6 = new Node(6); Node n7 = new Node(7); Node n8 = new Node(8); Node n9 = new Node(9); Node n10 = new Node(10); Node n11 = new Node(11); Node n12 = new Node(12); Node n13 = new Node(13); n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; n3.left = n6; n3.right = n7; n4.left = n4.right = null; n5.left = n10; n5.right = n11; n6.left = n6.right = null; n7.left = n8; n7.right = n9; n10.left = n12; n10.right = n13; n11.left = n11.right = null; n8.left = n8.right = null; n9.left = n9.right = null; inOrder(n1); postOrder(n1); /* * 1. we take the list of nodes that are in between them * 2. then we take the address of each node of the above found list * 3. the node that is in the farthest position, will be the LCA */ Node fn = n6; Node sn = n9; List<Node> inBetweenList = inBetween(inOrderList, fn, sn); System.out.println("The nodes in between " + fn + " and " + sn + " are as follows " + inBetweenList); } public static List<Node> inBetween(List<Node> inOrder, Node fn, Node sn){ int i1 = inOrder.indexOf(fn); int i2 = inOrder.indexOf(sn); List<Node> result = i1 > i2 ? inOrder.subList(i2, i1 + 1) : inOrder.subList(i1, i2 + 1); return result; } public static Node lca(List<Node> inBetweenList, List<Node> postOrderList){ Node result = null; int maxIndex = 0; for(Node node : inBetweenList){ maxIndex = postOrderList.indexOf(node) > maxIndex ? postOrderList.indexOf(node) : maxIndex; } result = postOrderList.get(maxIndex); return result; } public static void inOrder(Node root){ if(root == null){ return; } inOrder(root.left); inOrderList.add(root); inOrder(root.right); } public static void preOrder(Node root){ if(root == null){ return; } preOrderList.add(root); preOrder(root.left); preOrder(root.right); } public static void postOrder(Node root){ if(root == null){ return; } postOrder(root.left); postOrder(root.right); postOrderList.add(root); } } class Node{ public Node left; public Node right; public int info; public Node(int info){ this.info = info; this.left = null; this.left = null; } return "" + this.info; } }
Standard input is empty
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