BinaryTree VerticalOrder Traversal in JAVA

This is my implementation of the BinaryTree vertical order traversal. Vertical order traversal is an algorithm that groups all nodes with the same horizontal distance together. Horizontal distance is the amount of divergence a node has compared to its parent. For example, suppose a node has horizontal distance of 0, then its left child will have horizontal distance of the current node's horizontal distance - 1 and its right child will have horizontal distance of the current node's horizontal distance + 1. I am using a LinkedHashMap that maps Integer of horizontal distance to List of nodes with that particular horizontal distance in the order of insertion. Lastly, I am using inorder traversal to ensure that the left subtree gets inserted into the map first.

Implementation

public static void printVerticalOrder(TreeNode root) {
    if (root == null) return;

    Stack<TreeNode> parents = new Stack<TreeNode>();
    Map<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();

    TreeNode cur = root;
    while (!parents.isEmpty() || cur != null) {
        if (cur != null) {
            if (cur.left != null)
                cur.left.hd = cur.hd - 1;

            if (cur.right != null)
                cur.right.hd = cur.hd + 1;

            parents.push(cur);
            cur = cur.left;
        }
        else {
            TreeNode parent = parents.pop();

            if (!map.containsKey(parent.hd))
                map.put(parent.hd, new ArrayList<Integer>());

            map.get(parent.hd).add(parent.data);
            cur = parent.right;
        }
    }

    Iterator<Integer> keys = map.keySet().iterator();
    while (keys.hasNext()) {
        int key = keys.next();
        List<Integer> list = map.get(key);

        for (int i = 0; i < list.size(); i++) {
            System.out.printf("%d ", list.get(i));
        }

        System.out.println();
    }
}

This article is my 17th oldest. It is 238 words long, and it’s got 0 comments for now.