Code Implementation

from collections import defaultdict, deque

class Solution:
    def verticalOrder(self, root):
        if not root:
            return []
        column_table = defaultdict(list)
        queue = deque([(root, 0)])
        min_col = max_col = 0

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

        return [column_table[x] for x in range(min_col, max_col + 1)]
      

#include <vector>
#include <queue>
#include <map>
using namespace std;

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        map<int, vector<int>> columnTable;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        while (!q.empty()) {
            auto [node, col] = q.front(); q.pop();
            if (node) {
                columnTable[col].push_back(node->val);
                q.push({node->left, col-1});
                q.push({node->right, col+1});
            }
        }
        vector<vector<int>> result;
        for (auto& [col, nodes] : columnTable) {
            result.push_back(nodes);
        }
        return result;
    }
};
      

import java.util.*;

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Map<Integer, List<Integer>> columnTable = new HashMap<>();
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> colQueue = new LinkedList<>();
        int minCol = 0, maxCol = 0;

        nodeQueue.offer(root);
        colQueue.offer(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int col = colQueue.poll();

            columnTable.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);

            if (node.left != null) {
                nodeQueue.offer(node.left);
                colQueue.offer(col - 1);
            }
            if (node.right != null) {
                nodeQueue.offer(node.right);
                colQueue.offer(col + 1);
            }
        }

        for (int i = minCol; i <= maxCol; ++i) {
            result.add(columnTable.get(i));
        }
        return result;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalOrder = function(root) {
    if (!root) return [];
    let columnTable = new Map();
    let queue = [[root, 0]];
    let minCol = 0, maxCol = 0;

    while (queue.length) {
        let [node, col] = queue.shift();
        if (node) {
            if (!columnTable.has(col)) columnTable.set(col, []);
            columnTable.get(col).push(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);
            queue.push([node.left, col - 1]);
            queue.push([node.right, col + 1]);
        }
    }
    let result = [];
    for (let i = minCol; i <= maxCol; ++i) {
        result.push(columnTable.get(i));
    }
    return result;
};
      

Problem Description

Given the root of a binary tree, perform a vertical order traversal of its nodes' values. For each vertical column (from leftmost to rightmost), collect all the nodes that appear in that column from top to bottom. Return a list of lists, where each inner list contains the values of the nodes in a vertical column, ordered from left to right.

• Each node in the tree has a unique position determined by its horizontal distance from the root.
• If two nodes are in the same row and column, they should appear in the order they are encountered in a level order (BFS) traversal.
• The tree may be empty (i.e., root is null).

Thought Process

At first glance, the problem asks for a "vertical" grouping of nodes in a binary tree. This suggests we need to assign a "column" index to each node as we traverse the tree, so that nodes directly above or below each other (vertically) share the same column number.

A brute-force approach might be to traverse the tree and, for each node, determine its column and row, then sort all nodes by column and row. However, this is inefficient and unnecessarily complex.

Instead, we can perform a level order (BFS) traversal, keeping track of each node's column index. BFS ensures that when multiple nodes share the same column and row, they are added in the correct order (top to bottom, left to right). We can use a hash map (dictionary) to group node values by their column index.

After traversal, we simply output the values grouped by columns, sorted from the smallest to largest column index.

Solution Approach

The solution involves traversing the tree while assigning a column index to each node, and grouping nodes by column:

1. Assign Column Indices:
   • The root node is at column 0.
   • For any node at column c:
     • Its left child is at column c - 1.
     • Its right child is at column c + 1.
2. BFS Traversal:
   • Use a queue to traverse the tree in level order.
   • For each node, store its column index along with the node itself.
   • When visiting a node, append its value to the list corresponding to its column in a hash map.
3. Tracking Column Boundaries:
   • Keep track of the minimum and maximum column indices encountered during traversal.
   • This allows us to output the results in the correct left-to-right order at the end.
4. Output Construction:
   • Iterate from the smallest to largest column index, and collect the corresponding lists of node values.

Using a hash map for columns ensures O(1) insertion, and BFS guarantees the required top-to-bottom, left-to-right order.

Example Walkthrough

Consider the following binary tree:

         3
        / \
       9   8
      /   / \
     4   1   7
          \
           2
  

Let's trace the vertical order traversal:

• Start with root (3) at column 0: column_table[0] = [3]
• Left child (9) at column -1: column_table[-1] = [9]
• Right child (8) at column +1: column_table[1] = [8]
• 9's left child (4) at column -2: column_table[-2] = [4]
• 8's left child (1) at column 0: column_table[0] = [3, 1]
• 8's right child (7) at column 2: column_table[2] = [7]
• 1's right child (2) at column 1: column_table[1] = [8, 2]

The minimum column is -2, and the maximum is 2. The final output is:

• Column -2: [4]
• Column -1: [9]
• Column 0: [3, 1]
• Column 1: [8, 2]
• Column 2: [7]

Time and Space Complexity

• Brute-force approach:
  • Traverse the tree, record (node, row, col) for every node, then sort all nodes by column and row.
  • Time: O(N log N) due to sorting; Space: O(N) for storage.
• Optimized BFS approach:
  • Each node is visited exactly once: O(N) time.
  • Space: O(N) for the queue and hash map (since every node is stored once).
  • No sorting is needed, as columns are tracked during traversal.

Summary

The vertical order traversal problem can be solved efficiently using a breadth-first search (BFS) while maintaining a mapping from column indices to node values. By assigning columns as we traverse and grouping nodes accordingly, we ensure the correct vertical and top-to-bottom order. This approach is both simple and efficient, leveraging hash maps for grouping and BFS for ordering, making the solution elegant and practical for large trees.