987. Vertical Order Traversal of a Binary Tree

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Python

DFS than sort with different keys

from collections import defaultdict


class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        mapper = defaultdict(list)

        def dfs(node, level: int, pos: int):
            if not node:
                return

            dfs(node.left, level+1, pos-1)
            mapper[pos].append((level, node.val))
            dfs(node.right, level+1, pos+1)

        dfs(root, 0, 0)

        result = []
        for key in sorted(mapper.keys()):
            result.append([num for level, num in sorted(mapper[key])])
        return result

Javascript

var verticalTraversal = function(root) {
    const queue = [];
    const tmp = [];
    let start = Infinity;
    queue.push([0, 0, root]);

    while (queue.length) {
        const [row, col, node] = queue.shift();

        tmp.push([row, col, node.val]);
        start = Math.min(col, start)

        if (node.left) queue.push([row + 1, col - 1, node.left]);
        if (node.right) queue.push([row + 1, col + 1, node.right]);
    }

    tmp.sort((a, b) => {
        // compare col
        if (a[1] === b[1]) {
            // compare row
            if (a[0] === b[0]) {
                // compare val
                return a[2] - b[2];
            } else {
                return a[0] - b[0];
            }
        } else {
            return a[1] - b[1]
        }
    });

    const res = [];
    let inc = Math.abs(start);

    for (const [,col, val] of tmp) {
        const idx = col + inc;

        if (res[idx] !== undefined) res[idx].push(val);
        else res.push([val]);
    }

    return res;
};