Print the Binary Tree in Vertical Order Path.

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]