Create binary tree in Vertical Order

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;

class Node {
	int key;
	Node left, right;
	// A utility function to create a new node
	Node newNode(int key)
	{
		Node node = new Node();
		node.key = key;
		node.left = node.right = null;
		return node;
	}
}

class Qobj {
	int hd;
	Node node;
	Qobj(int hd, Node node)
	{
		this.hd = hd;
		this.node = node;
	}
}

public class VerticalOrderTraversal {

	// The main function to print vertical order of a
	// binary tree with given root
	static void printVerticalOrder(Node root)
	{
		// Base case
		if (root == null)
			return;

		// Create a map and store vertical order in
		// map using function getVerticalOrder()
		TreeMap<Integer, ArrayList<Integer> > m = new TreeMap<>();
		int hd = 0;

		// Create queue to do level order traversal.
		// Every item of queue contains node and
		// horizontal distance.
		Queue<Qobj> que = new LinkedList<Qobj>();
		que.add(new Qobj(0, root));

		while (!que.isEmpty()) {
			// pop from queue front
			Qobj temp = que.poll();
			hd = temp.hd;
			Node node = temp.node;

			// insert this node's data in array of hash
			if (m.containsKey(hd)) {
				m.get(hd).add(node.key);
			}
			else {
				ArrayList<Integer> al = new ArrayList<>();
				al.add(node.key);
				m.put(hd, al);
			}
			if (node.left != null)
				que.add(new Qobj(hd - 1, node.left));
			if (node.right != null)
				que.add(new Qobj(hd + 1, node.right));
		}

		// Traverse the map and print nodes at
		// every horizontal distance (hd)
		for (Map.Entry<Integer, ArrayList<Integer> > entry : m.entrySet()) {
			ArrayList<Integer> al = entry.getValue();
			for (Integer i : al)
				System.out.print(i + " ");
			System.out.println();
		}
	}

	// Driver program to test above functions
	public static void main(String ar[])
	{
		Node n = new Node();
		Node root;
		root = n.newNode(1);
		root.left = n.newNode(2);
		root.right = n.newNode(3);
		root.left.left = n.newNode(4);
		root.left.right = n.newNode(5);
		root.right.left = n.newNode(6);
		root.right.right = n.newNode(7);
		root.right.left.right = n.newNode(8);
		root.right.right.right = n.newNode(9);
		root.right.right.left = n.newNode(10);
		root.right.right.left.right = n.newNode(11);
		root.right.right.left.right.right = n.newNode(12);
		System.out.println("Vertical order traversal is ");
		printVerticalOrder(root);
	}
}