Vertical Order Traversal of a Binary Tree

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int,int,int>> nodes;       // (col, row, val)
        function<void(TreeNode*,int,int)> dfs = [&](TreeNode* n, int r, int c) {
            if (!n) return;
            nodes.emplace_back(c, r, n->val);
            dfs(n->left,  r + 1, c - 1);
            dfs(n->right, r + 1, c + 1);
        };
        dfs(root, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> ans;
        int prevCol = INT_MIN;
        for (auto& [c, r, v] : nodes) {
            if (c != prevCol) { ans.push_back({}); prevCol = c; }
            ans.back().push_back(v);
        }
        return ans;
    }
};

import (
    "math"
    "sort"
)

func verticalTraversal(root *TreeNode) [][]int {
    type entry struct{ c, r, v int }
    var nodes []entry
    var dfs func(n *TreeNode, r, c int)
    dfs = func(n *TreeNode, r, c int) {
        if n == nil {
            return
        }
        nodes = append(nodes, entry{c, r, n.Val})
        dfs(n.Left, r+1, c-1)
        dfs(n.Right, r+1, c+1)
    }
    dfs(root, 0, 0)
    sort.Slice(nodes, func(i, j int) bool {
        if nodes[i].c != nodes[j].c {
            return nodes[i].c < nodes[j].c
        }
        if nodes[i].r != nodes[j].r {
            return nodes[i].r < nodes[j].r
        }
        return nodes[i].v < nodes[j].v
    })
    ans := [][]int{}
    prevCol := math.MinInt32
    for _, e := range nodes {
        if e.c != prevCol {
            ans = append(ans, []int{})
            prevCol = e.c
        }
        ans[len(ans)-1] = append(ans[len(ans)-1], e.v)
    }
    return ans
}

from typing import List, Optional

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        nodes: list[tuple[int, int, int]] = []  # (col, row, val)

        def dfs(n: Optional[TreeNode], r: int, c: int) -> None:
            if n is None:
                return
            nodes.append((c, r, n.val))
            dfs(n.left, r + 1, c - 1)
            dfs(n.right, r + 1, c + 1)

        dfs(root, 0, 0)
        nodes.sort()
        ans: List[List[int]] = []
        prev_col = float('-inf')
        for c, _r, v in nodes:
            if c != prev_col:
                ans.append([])
                prev_col = c
            ans[-1].append(v)
        return ans

function verticalTraversal(root) {
    const nodes = []; // [col, row, val]
    const dfs = (n, r, c) => {
        if (!n) return;
        nodes.push([c, r, n.val]);
        dfs(n.left, r + 1, c - 1);
        dfs(n.right, r + 1, c + 1);
    };
    dfs(root, 0, 0);
    nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    const ans = [];
    let prevCol = -Infinity;
    for (const [c, , v] of nodes) {
        if (c !== prevCol) { ans.push([]); prevCol = c; }
        ans[ans.length - 1].push(v);
    }
    return ans;
}

class Solution {
    private List<int[]> nodes = new ArrayList<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        nodes.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        List<List<Integer>> ans = new ArrayList<>();
        int prevCol = Integer.MIN_VALUE;
        for (int[] e : nodes) {
            if (e[0] != prevCol) {
                ans.add(new ArrayList<>());
                prevCol = e[0];
            }
            ans.get(ans.size() - 1).add(e[2]);
        }
        return ans;
    }

    private void dfs(TreeNode n, int r, int c) {
        if (n == null) return;
        nodes.add(new int[]{c, r, n.val});
        dfs(n.left, r + 1, c - 1);
        dfs(n.right, r + 1, c + 1);
    }
}

function verticalTraversal(root: TreeNode | null): number[][] {
    const nodes: [number, number, number][] = []; // [col, row, val]
    const dfs = (n: TreeNode | null, r: number, c: number): void => {
        if (!n) return;
        nodes.push([c, r, n.val]);
        dfs(n.left, r + 1, c - 1);
        dfs(n.right, r + 1, c + 1);
    };
    dfs(root, 0, 0);
    nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    const ans: number[][] = [];
    let prevCol = -Infinity;
    for (const [c, , v] of nodes) {
        if (c !== prevCol) { ans.push([]); prevCol = c; }
        ans[ans.length - 1].push(v);
    }
    return ans;
}