https://hack.codingblocks.com/app/contests/1968/78/problem
class BinaryTree{
private class Node{
int data;
Node left;
Node right;
}
private Node root;
int vidx = 0;
public BinaryTree() {
construct();
}
private void construct() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Queue<Node> h = new LinkedList<>();
int n = sc.nextInt();
Node nn = new Node();
nn.data = n;
root = nn;
h.add(nn);
while (!h.isEmpty()) {
int child1 = sc.nextInt();
int child2 = sc.nextInt();
Node nn1 = new Node();
Node nn2 = new Node();
if (child1 != -1)
nn1.data = child1;
else
nn1 = null;
if (child2 != -1)
nn2.data = child2;
else
nn2 = null;
if (nn1 != null)
h.add(nn1);
if (nn2 != null)
h.add(nn2);
Node rn = h.remove();
rn.left = nn1;
rn.right = nn2;
}
}
private class VOPair {
Node node;
int vl;
public VOPair(Node node, int vl) {
this.node = node;
this.vl = vl;
}
@Override
public String toString() {
return node.data + " -> " + vl;
}
}
public void verticalOrderTraversal() {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
Queue<VOPair> q = new LinkedList<>();
VOPair sp = new VOPair(root, 0);
q.add(sp);
while (!q.isEmpty()) {
VOPair rp = q.remove();
if (!map.containsKey(rp.vl))
map.put(rp.vl, new ArrayList<>());
map.get(rp.vl).add(rp.node.data);
if (rp.node.left != null) {
VOPair lcp = new VOPair(rp.node.left, rp.vl - 1);
q.add(lcp);
}
if (rp.node.right != null) {
VOPair rcp = new VOPair(rp.node.right, rp.vl + 1);
q.add(rcp);
}
}
ArrayList<Integer> keys = new ArrayList<Integer>(map.keySet());
Collections.sort(keys);
for (int key : keys) {
for (int i = 0; i < map.get(key).size(); i++) {
System.out.print(map.get(key).get(i) + " ");
}
System.out.println();
}
}
}