Vertical Level order traversal of Binary Tree. | Java solution

Dear Friends,

I am with you with a data structure and algorithmic problem based on Binary tree and Hashing.

Given a binary tree we need to print the nodes according to vertical level ordering.



For above Binary tree the vertical level ordering is as below
4
2
1 5 6
3 8
7
9

Lets try to analyze the above binary tree  

1. Lets record the horizontal (left, right) distance of each node from root
2. To record horizontal distance for a node from root , lets see as how many lefts and how many rights do we need to travel from root's horizontal position to reach the node's horizontal position.
3. Lets take 1 Left step as -1 and 1 Right step as +1.

Node	Horizontal distance of Node from Root
Node with value 1 (root)	0	Root => 0
Node with value 2	-1	0 + (-1) = -1
Node with value 4	-2	-1+(-1) = -2
Node with value 5	0	-1 + 1= 0
Node with value 3	+1	0 + 1 = +1
Node with value 6	0	+1 +(-1) = 0
Node with value 8	+1	0 +1 = +1
Node with value 7	+2	+1 +1 = +2
Node with value 9	+3	2+1 = +3

With above analysis lets see the code in java for the solution of this problem.

package krishnalearnings.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class VerticalLevelOrderTraversal {
    public static class Node {
        private Node left;
        private Node right;
        private int data;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        // lets construct a tree
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node3 = new Node(3);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node6.right = node8;
        node7.right = node9;
        // tree constructed
        printVerticalLevelOrder(root);
    }

    private static void printVerticalLevelOrder(Node root) {
        TreeMap<Integer, List<Node>> map = new TreeMap<>();
        initilizeMap(root, 0, map);
        Set<Integer> horizontalDistances = map.keySet();
        for (Integer distance : horizontalDistances) {
            for (Node node : map.get(distance)) {
                System.out.print(node.data + " ");
            }
            System.out.println();
        }
    }

    private static void initilizeMap(Node root, int horizontalDistance, Map<Integer, List<Node>> map) {
        if (root != null) {
            List<Node> list = map.get(horizontalDistance);
            if (list == null) {
                list = new ArrayList<>();
                map.put(horizontalDistance, list);
            }
            list.add(root);
            initilizeMap(root.left, horizontalDistance - 1, map);
            initilizeMap(root.right, horizontalDistance + 1, map);
        }
    }
}