Objective: – Given a binary tree, print it in vertical order path.
What is Vertical Order
as you can see in the example above, [4],[2], [1,5,6],[3],[7] are the verical order of the given binary tree.
Approach:
- Its a tricky solution.
- Do the preordertraversal.
- Take a variable called level, when ever you go left, do level++ AND when ever you go right do level–.
- With step above we have separated out the levels vertically.
- Now you need to store the elements of each level, so create a TreeMap and the (key,value) pair will be (level,elements at that level).
- At the end iterate through the TreeMap and print the results.
Complete Code:
| import java.util.ArrayList; | |
| import java.util.Set; | |
| import java.util.TreeMap; | |
| public class VerticalOrder { | |
| public static TreeMap<Integer, ArrayList> ht = new TreeMap<>(); | |
| public ArrayList<Integer> al; | |
| public void vertical(Node root, int level) { | |
| if (root == null) { | |
| return; | |
| } | |
| if (ht.containsKey(level)) { | |
| ArrayList x = ht.get(level); | |
| x.add(root.data); | |
| ht.put(level, x); | |
| } else { | |
| al = new ArrayList<>(); | |
| al.add(root.data); | |
| ht.put(level, al); | |
| } | |
| vertical(root.left, level–1); | |
| vertical(root.right, level+1); | |
| } | |
| public void printResult(TreeMap ht) { | |
| Set<Integer> i = ht.keySet(); | |
| for (int keys : i) { | |
| System.out.println(ht.get(keys)); | |
| } | |
| } | |
| public static void main(String args[]) { | |
| Node root = new Node(1); | |
| root.left = new Node(2); | |
| root.right = new Node(3); | |
| root.left.left = new Node(4); | |
| root.left.right = new Node(5); | |
| root.right.left = new Node(6); | |
| root.right.right = new Node(7); | |
| VerticalOrder p = new VerticalOrder(); | |
| p.vertical(root, 0); | |
| p.printResult(ht); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| left = null; | |
| right = null; | |
| } | |
| } | |
Output:
[4] [2] [1, 5, 6] [3] [7]