Vertical Order Traversal of a Binary Tree

hard tree dfs hash map sorting

Problem

For each node compute (col, row); group nodes by col (left → right), then within a column sort by row then by value. Return the columns.

Inputtree = [3,9,20,null,null,15,7]

Output[[9],[3,15],[20],[7]]

DFS pushing children with col±1, row+1.

level-order (use 'null')

from collections import defaultdict
def verticalTraversal(root):
    nodes = defaultdict(list)
    def dfs(n, r, c):
        if not n: return
        nodes[c].append((r, n.val))
        dfs(n.left, r + 1, c - 1)
        dfs(n.right, r + 1, c + 1)
    dfs(root, 0, 0)
    out = []
    for c in sorted(nodes):
        nodes[c].sort()
        out.append([v for _, v in nodes[c]])
    return out

function verticalTraversal(root) {
  const nodes = new Map();
  (function dfs(n, r, c) {
    if (!n) return;
    if (!nodes.has(c)) nodes.set(c, []);
    nodes.get(c).push([r, n.val]);
    dfs(n.left, r + 1, c - 1);
    dfs(n.right, r + 1, c + 1);
  })(root, 0, 0);
  const cols = [...nodes.keys()].sort((a, b) => a - b);
  return cols.map(c => {
    nodes.get(c).sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    return nodes.get(c).map(x => x[1]);
  });
}

class Solution {
    TreeMap<Integer, List<int[]>> cols = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        List<List<Integer>> out = new ArrayList<>();
        for (var entry : cols.entrySet()) {
            entry.getValue().sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
            List<Integer> col = new ArrayList<>();
            for (int[] p : entry.getValue()) col.add(p[1]);
            out.add(col);
        }
        return out;
    }
    void dfs(TreeNode n, int r, int c) {
        if (n == null) return;
        cols.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{ r, n.val });
        dfs(n.left, r + 1, c - 1); dfs(n.right, r + 1, c + 1);
    }
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
    map<int, vector<pair<int, int>>> cols;
    function<void(TreeNode*, int, int)> dfs = [&](TreeNode* n, int r, int c) {
        if (!n) return;
        cols[c].push_back({r, n->val});
        dfs(n->left, r + 1, c - 1); dfs(n->right, r + 1, c + 1);
    };
    dfs(root, 0, 0);
    vector<vector<int>> out;
    for (auto& [c, vec] : cols) {
        sort(vec.begin(), vec.end());
        vector<int> col;
        for (auto& p : vec) col.push_back(p.second);
        out.push_back(col);
    }
    return out;
}

Explanation

Imagine laying the tree on graph paper. Each node gets a column c (left moves to c - 1, right to c + 1) and a row r (each step down is r + 1). The answer is the nodes grouped left-to-right by column.

The code does a simple DFS from the root, and for every node it records the triple (row, value) into a bucket keyed by its column. The root starts at (r=0, c=0), and children get their coordinates passed down recursively.

After collecting everyone, we go through the columns in sorted order. Within a single column there can be ties (two nodes at the same spot), so we sort each column's list by row first, then by value to break ties, and finally pull out just the values.

Example: [3, 9, 20, null, null, 15, 7]. Node 3 is at column 0, 9 at -1, 20 at +1, 15 at 0, 7 at +2. Grouping and sorting gives columns [[9], [3, 15], [20], [7]].

The sorting per column is what makes this O(n log n); the DFS itself just visits each node once.

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