Problem Statement

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

Solution Explanation

Given a binary tree,

                        35
                       /   \
                      23    27
                     /  \     \
                    14   10    9
                      

vertical order traversal looks like this,

        [[14],
         [23],
         [35,10],
         [27],
         [9]]

To traverse nodes and print in this order, we will need to keep track of the columns and identify which column does each node belong to. As you can see, the left most node in the tree is 14, which is also the first column.

If we consider that the root node 35 is at col 0, then 14 is at col -2 and 23 is at -1. Using this logic, we can do a in order traversal, decrease col by 1 when passing the left node to the recursive function and increase the col value by 1 when passing to the right node. While doing this, we can use a map to group nodes based on the column value.

Below is the code in java which does the vertical level order traversal,

    
    	public static List<List<Integer>> verticalOrderTreeTraversal(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if (root == null)
			return result;
		Queue<TreeNode> queue = new LinkedList<>();
		Queue<Integer> cols = new LinkedList<>();
		Map<Integer, ArrayList<Integer>> map = new HashMap<>();
		queue.add(root);
		cols.add(0);
		int min = 0, max = 0;
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			int col = cols.poll();
			map.putIfAbsent(col, new ArrayList<Integer>());
			map.get(col).add(node.val);
			if (node.left != null) {
				queue.add(node.left);
				cols.add(col - 1);
				min = Math.min(min, col - 1);
			}
			if (node.right != null) {
				queue.add(node.right);
				cols.add(col + 1);
				max = Math.max(max, col + 1);
			}
		}
		for (int i = min; i < max; i++) {
			result.add(map.get(i));
		}

		return result;
	}

Time Complexity

We will do a single traversal of the tree starting from the root, so the time complexity will be O(n) and space complexity is O(n)(n for each of the queues and a map which basically adds up to O(n)).