314. Binary Tree Vertical Order Traversal

Published on August 26, 2023

Question

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

If two nodes are in the same row and column, the order should be from left to right.

Example:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Algorithm

This question, I did it 10 days ago with error.

And today I did it with one pass and is the standard answer. Interesting.

Basically we traverse all the node and keep its column number at the same time. The logic is left child is root's column number minus one and right child column number is root column number plus one.

Each time we get the node from our traversal we put it into corresponding list.

Finally we sort the column number existing and output them. There's a smart way that we can eliminate the sorting is that: instead sorting the keys, we only keep updating the left and right bound( max and min column), then finally output by the order of column number.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0));
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> ele = queue.poll();
            TreeNode node = ele.getKey();
            Integer col = ele.getValue();
            List<Integer> list = map.getOrDefault(col, new ArrayList<>());
            list.add(node.val);
            map.put(col, list);
            if (node.left != null) {
                queue.offer(new Pair(node.left, col - 1));
            }
            if (node.right != null) {
                queue.offer(new Pair(node.right, col + 1));
            }   
        }
        SortedSet<Integer> keys = new TreeSet<>(map.keySet());
        for (Integer key : keys) {
            res.add(new ArrayList<>(map.get(key)));
        }
        return res;
    }
}