Vertical Order Traversal of a Binary Tree

// C++
vector<vector<int>> verticalTraversal(TreeNode* root) {
    map<int, map<int, multiset<int>>> mp; // col -> row -> vals
    queue<tuple<TreeNode*, int, int>> q;
    q.push({root, 0, 0});
    while (!q.empty()) {
        auto [node, row, col] = q.front(); q.pop();
        mp[col][row].insert(node->val);
        if (node->left)  q.push({node->left,  row+1, col-1});
        if (node->right) q.push({node->right, row+1, col+1});
    }
    vector<vector<int>> res;
    for (auto& [col, rows] : mp) {
        res.push_back({});
        for (auto& [row, vals] : rows)
            res.back().insert(res.back().end(), vals.begin(), vals.end());
    }
    return res;
}

// Java
public List<List<Integer>> verticalTraversal(TreeNode root) {
    TreeMap<Integer, TreeMap<Integer, List<Integer>>> mp = new TreeMap<>();
    Queue<int[]> q = new LinkedList<>(); // [node encoded via map, row, col]
    Map<Integer, TreeNode> nodeMap = new HashMap<>();
    // simplified: use object array
    Queue<Object[]> queue = new LinkedList<>();
    queue.add(new Object[]{root, 0, 0});
    while (!queue.isEmpty()) {
        Object[] cur = queue.poll();
        TreeNode node = (TreeNode) cur[0];
        int row = (int) cur[1], col = (int) cur[2];
        mp.computeIfAbsent(col, k -> new TreeMap<>())
          .computeIfAbsent(row, k -> new ArrayList<>()).add(node.val);
        if (node.left != null)  queue.add(new Object[]{node.left,  row+1, col-1});
        if (node.right != null) queue.add(new Object[]{node.right, row+1, col+1});
    }
    List<List<Integer>> res = new ArrayList<>();
    for (var colMap : mp.values()) {
        List<Integer> col = new ArrayList<>();
        for (var rowList : colMap.values()) {
            Collections.sort(rowList);
            col.addAll(rowList);
        }
        res.add(col);
    }
    return res;
}

// JavaScript
function verticalTraversal(root) {
    const nodes = [];
    const queue = [[root, 0, 0]];
    while (queue.length) {
        const [node, row, col] = queue.shift();
        nodes.push([col, row, node.val]);
        if (node.left)  queue.push([node.left,  row+1, col-1]);
        if (node.right) queue.push([node.right, row+1, col+1]);
    }
    nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    const result = [];
    let prevCol = null;
    for (const [col, , val] of nodes) {
        if (col !== prevCol) { result.push([]); prevCol = col; }
        result[result.length - 1].push(val);
    }
    return result;
}

# Python
from collections import deque

def verticalTraversal(root):
    nodes = []
    q = deque([(root, 0, 0)])
    while q:
        node, row, col = q.popleft()
        nodes.append((col, row, node.val))
        if node.left:  q.append((node.left,  row + 1, col - 1))
        if node.right: q.append((node.right, row + 1, col + 1))
    nodes.sort()
    result, prev_col = [], None
    for col, _, val in nodes:
        if col != prev_col:
            result.append([])
            prev_col = col
        result[-1].append(val)
    return result