0314.md

314. Binary Tree Vertical Order Traversal

Level:

Topic:

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.

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Intuition

The most intuitive way is to use bfs, level order traversal. Because it's already from top to bottom and left to right.

Starting from the root, it's at column 0 and it's left child is at column -1 and right child at column 1.

Iterative:

• use a hashmap to store every column's list of node value
• use a queue of pair to traverse the tree and add to map based on its column index
• instead of sorting, make note of the minimum column index

Recursive:

• similar to iterative, but has to store every node to hashmap to deal with level traverse problem
• when adding to the final list, sort the list based on its level

Code

Time: O(n)
Space: O(n)

Iterative

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();

    int minIndex = 0;
    HashMap<Integer, List<Integer>> map = new HashMap<>();

    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
    if (root != null)
        queue.add(new Pair<>(root, 0));

    while (!queue.isEmpty()) {
        Pair<TreeNode, Integer> p = queue.poll();
        TreeNode node = p.getKey();
        int col = p.getValue();

        if (!map.containsKey(col))
            map.put(col, new ArrayList<>());

        minIndex = Math.min(col, minIndex);
        map.get(col).add(node.val);

        if (node.left != null)
            queue.add(new Pair<>(node.left, col-1));
        if (node.right != null)
            queue.add(new Pair<>(node.right, col+1));
    }

    while (map.containsKey(minIndex)) {
        ans.add(map.get(minIndex++));
    }

    return ans;
}

Time: O(n log n), sort used O(log n)
Space: O(n)

Recursive

HashMap<TreeNode, Integer> nodePosition = new HashMap<>();
HashMap<Integer, List<TreeNode>> map = new HashMap<>();
int minIndex = 0;

public List<List<Integer>> verticalOrder(TreeNode root) {
    traverse(root, 0, 0);
    List<List<Integer>> ans = new ArrayList<>();
    while (map.containsKey(minIndex)) {
        Collections.sort(map.get(minIndex),
                    (a,b) -> nodePosition.get(a) - nodePosition.get(b));
        List<Integer> col = new ArrayList<>();
        for (TreeNode node: map.get(minIndex))
            col.add(node.val);

        ans.add(col);
        minIndex++;
    }

    return ans;
}

private void traverse(TreeNode root, int index, int level) {
    if (root == null)
        return;

    minIndex = Math.min(minIndex, index);
    if (!map.containsKey(index))
        map.put(index, new ArrayList<>());

    nodePosition.put(root, level);
    map.get(index).add(root);

    traverse(root.left, index-1, level+1);
    traverse(root.right, index+1, level+1);
}