Vertical Order Traversal of a Binary Tree solution and explanation

from collections import defaultdict, deque

def verticalOrderTraversal(root):
    if not root:
        return []

    col_table = defaultdict(list)
    min_col = max_col = 0
    queue = deque([(root, 0, 0)])  # node, row, column

    while queue:
        node, row, col = queue.popleft()
        if node:
            col_table[col].append((row, node.val))
            min_col = min(min_col, col)
            max_col = max(max_col, col)
            queue.append((node.left, row + 1, col - 1))
            queue.append((node.right, row + 1, col + 1))

    result = []
    for col in range(min_col, max_col + 1):
        # Sort by row and then by value
        col_table[col].sort(key=lambda x: (x[0], x[1]))
        result.append([val for row, val in col_table[col]])

    return result

import java.util.*;

public class Solution {
    class NodeInfo {
        TreeNode node;
        int row;
        int col;

        public NodeInfo(TreeNode node, int row, int col) {
            this.node = node;
            this.row = row;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalOrderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, List<int[]>> columnTable = new HashMap<>();
        Queue<NodeInfo> queue = new LinkedList<>();
        int minCol = 0, maxCol = 0;

        queue.offer(new NodeInfo(root, 0, 0));

        while (!queue.isEmpty()) {
            NodeInfo ni = queue.poll();
            TreeNode node = ni.node;
            int row = ni.row, col = ni.col;

            if (!columnTable.containsKey(col)) columnTable.put(col, new ArrayList<>());
            columnTable.get(col).add(new int[]{row, node.val});

            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);

            if (node.left != null) queue.offer(new NodeInfo(node.left, row + 1, col - 1));
            if (node.right != null) queue.offer(new NodeInfo(node.right, row + 1, col + 1));
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int col = minCol; col <= maxCol; col++) {
            List<int[]> list = columnTable.get(col);
            list.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
            List<Integer> currentColumn = new ArrayList<>();
            for (int[] entry : list) {
                currentColumn.add(entry[1]);
            }
            result.add(currentColumn);
        }

        return result;
    }
}

#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

map<int, vector<pair<int, int>>> col_table;

double min_col = 0, max_col = 0;

diagnostics Queue<pair<TreeNode*, pair<int, int>>> queue;

queue.push_back(make_pair(root, make_pair(0, 0)));
while (!queue.empty()) {
    auto [node, p] = queue.front();
    queue.pop_front();
    int row = p.first, col = p.second;
    col_table[col].emplace_back(row, node->val);
    min_col = min(min_col, col);
    max_col = max(max_col, col);
    if (node->left) queue.push_back(make_pair(node->left, make_pair(row + 1, col - 1)));
    if (node->right) queue.push_back(make_pair(node->right, make_pair(row + 1, col + 1)));
}

vector<vector<int>> result;
for (int col = min_col; col <= max_col; ++col) {
    sort(col_table[col].begin(), col_table[col].end());
    vector<int> col_vals;
    for (auto [row, val] : col_table[col]) {
        col_vals.push_back(val);
    }
    result.push_back(col_vals);
}

def verticalOrderTraversal(root):
    node_list = []

    def DFS(node, row, col):
        if node is not None:
            node_list.append((col, row, node.val))
            DFS(node.left, row + 1, col - 1)
            DFS(node.right, row + 1, col + 1)

    DFS(root, 0, 0)
    node_list.sort()

    res = defaultdict(list)
    for col, row, value in node_list:
        res[col].append(value)

    return [res[x] for x in sorted(res)]

import java.util.*;

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

    private void DFS(TreeNode node, int row, int col) {
        if (node == null) return;
        nodeList.add(new int[]{col, row, node.val});
        DFS(node.left, row + 1, col - 1);
        DFS(node.right, row + 1, col + 1);
    }

    public List<List<Integer>> verticalOrderTraversal(TreeNode root) {
        DFS(root, 0, 0);
        Collections.sort(nodeList, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            else if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
            else return Integer.compare(a[2], b[2]);
        });

        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> columnTable = new TreeMap<>();

        for (int[] entry : nodeList) {
            int col = entry[0], row = entry[1], value = entry[2];
            columnTable.putIfAbsent(col, new ArrayList<>());
            columnTable.get(col).add(value);
        }

        return new ArrayList<>(columnTable.values());
    }
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function verticalTraversal(root: TreeNode | null): number[][] {
    const nodes: [number, number, number][] = [];
    const dfs = (root: TreeNode | null, i: number, j: number) => {
        if (!root) {
            return;
        }
        nodes.push([j, i, root.val]);
        dfs(root.left, i + 1, j - 1);
        dfs(root.right, i + 1, j + 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 prev = -2000;
    for (const [j, _, val] of nodes) {
        if (j !== prev) {
            prev = j;
            ans.push([]);
        }
        ans.at(-1)!.push(val);
    }
    return ans;
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalTraversal(root *TreeNode) (ans [][]int) {
	nodes := [][3]int{}
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, i, j int) {
		if root == nil {
			return
		}
		nodes = append(nodes, [3]int{j, i, root.Val})
		dfs(root.Left, i+1, j-1)
		dfs(root.Right, i+1, j+1)
	}
	dfs(root, 0, 0)
	sort.Slice(nodes, func(i, j int) bool {
		a, b := nodes[i], nodes[j]
		return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
	})
	prev := -2000
	for _, node := range nodes {
		j, val := node[0], node[2]
		if j != prev {
			ans = append(ans, nil)
			prev = j
		}
		ans[len(ans)-1] = append(ans[len(ans)-1], val)
	}
	return
}