|
| 1 | +package DataStructures.Trees; |
| 2 | + |
| 3 | +import java.util.ArrayList; |
| 4 | +import java.util.HashMap; |
| 5 | +import java.util.LinkedList; |
| 6 | +import java.util.Map; |
| 7 | +import java.util.Queue; |
| 8 | + |
| 9 | +/* The following class implements a vertical order traversal |
| 10 | +in a tree from top to bottom and left to right, so for a tree : |
| 11 | + 1 |
| 12 | + / \ |
| 13 | + 2 3 |
| 14 | + / \ \ |
| 15 | + 4 5 6 |
| 16 | + \ / \ |
| 17 | + 7 8 10 |
| 18 | + \ |
| 19 | + 9 |
| 20 | + the sequence will be : |
| 21 | + 4 2 7 1 5 9 3 8 6 10 |
| 22 | + */ |
| 23 | +public class VerticalOrderTraversal{ |
| 24 | + |
| 25 | + |
| 26 | + public static void main(String[] args) { |
| 27 | + BinaryTree tree = new BinaryTree(); |
| 28 | + tree.put(5); |
| 29 | + tree.put(6); |
| 30 | + tree.put(3); |
| 31 | + tree.put(1); |
| 32 | + tree.put(4); |
| 33 | + BinaryTree.Node root = tree.getRoot(); |
| 34 | + ArrayList<Integer> ans = verticalTraversal(root); |
| 35 | + for(int i : ans) { |
| 36 | + System.out.print(i+" "); |
| 37 | + } |
| 38 | + } |
| 39 | + |
| 40 | + /*Function that receives a root Node and prints the tree |
| 41 | + in Vertical Order.*/ |
| 42 | + private static ArrayList<Integer> verticalTraversal(BinaryTree.Node root) { |
| 43 | + /*Queue to store the Nodes.*/ |
| 44 | + Queue<BinaryTree.Node> queue= new LinkedList<>(); |
| 45 | + |
| 46 | + /*Queue to store the index of particular vertical |
| 47 | + column of a tree , with root at 0, Nodes on left |
| 48 | + with negative index and Nodes on right with positive |
| 49 | + index. */ |
| 50 | + Queue<Integer> index = new LinkedList<>(); |
| 51 | + |
| 52 | + /*Map of Integer and ArrayList to store all the |
| 53 | + elements in a particular index in a single arrayList |
| 54 | + that will have a key equal to the index itself. */ |
| 55 | + Map<Integer,ArrayList<Integer>> map = new HashMap<>(); |
| 56 | + |
| 57 | + /* min and max stores leftmost and right most index to |
| 58 | + later print the tree in vertical fashion.*/ |
| 59 | + int max =0, min =0; |
| 60 | + queue.offer(root); |
| 61 | + index.offer(0); |
| 62 | + |
| 63 | + while(!queue.isEmpty()) { |
| 64 | + |
| 65 | + if(queue.peek().left!=null) { |
| 66 | + /*Adding the left Node if it is not null |
| 67 | + and its index by subtracting 1 from it's |
| 68 | + parent's index*/ |
| 69 | + queue.offer(queue.peek().left); |
| 70 | + index.offer(index.peek()-1); |
| 71 | + } |
| 72 | + if(queue.peek().right!=null) { |
| 73 | + /*Adding the right Node if it is not null |
| 74 | + and its index by adding 1 from it's |
| 75 | + parent's index*/ |
| 76 | + queue.offer(queue.peek().right); |
| 77 | + index.offer(index.peek()+1); |
| 78 | + } |
| 79 | + /*If the map does not contains the index a new |
| 80 | + ArrayList is created with the index as key.*/ |
| 81 | + if(!map.containsKey(index.peek())) { |
| 82 | + ArrayList<Integer> a = new ArrayList<>(); |
| 83 | + map.put(index.peek(), a); |
| 84 | + } |
| 85 | + /*For a index, corresponding Node data is added |
| 86 | + to the respective ArrayList present at that |
| 87 | + index. */ |
| 88 | + map.get(index.peek()).add(queue.peek().data); |
| 89 | + max = (int)Math.max(max,index.peek()); |
| 90 | + min = (int)Math.min(min,index.peek()); |
| 91 | + /*The Node and its index are removed |
| 92 | + from their respective queues.*/ |
| 93 | + index.poll();queue.poll(); |
| 94 | + } |
| 95 | + /*Finally map data is printed here which has keys |
| 96 | + from min to max. Each ArrayList represents a |
| 97 | + vertical column that is added in ans ArrayList.*/ |
| 98 | + ArrayList<Integer> ans= new ArrayList<>(); |
| 99 | + for(int i =min ; i<= max ; i++) { |
| 100 | + for(int j = 0 ; j<map.get(i).size(); j++) { |
| 101 | + ans.add(map.get(i).get(j)); |
| 102 | + } |
| 103 | + } |
| 104 | + return ans; |
| 105 | + } |
| 106 | +} |
0 commit comments