Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9
Column  0: Nodes 3 and 15
Column  1: Only node 20
Column  2: Only node 7

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Thinking Process

Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS (this problem) O(n) O(w) Process by depth/layer

Solution

Solution: BFS with Column Tracking

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> rtn;
        if(!root) return rtn;
        map<int, vector<int>> map;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        while(!q.empty()) {
            int size = q.size();
            for(int i = 0; i < (int)q.size(); i++) {
                TreeNode* curr = q.front().first;
                int dir = q.front().second;
                q.pop();
                map[dir].push_back(curr->val);
                if(curr->left) q.push({curr->left, dir - 1});
                if(curr->right) q.push({curr->right, dir + 1});
            }
        }
        for(auto& [node, vals]: map) {
            rtn.push_back(vals);
        }
        return rtn;
    }
};

Solution Explanation

Approach: Level-order BFS (this problem)

Key idea: Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

How the code works:

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.

Walkthrough — input root = [3,9,20,null,null,15,7], expected output [[9],[3,15],[20],[7]]:

Column -1: Only node 9 Column 0: Nodes 3 and 15 Column 1: Only node 20 Column 2: Only node 7

Algorithm Explanation:

  1. Initialize: Create empty result vector and map for column grouping
  2. BFS setup: Start with root at column 0
  3. Level processing: For each level, process all nodes at that level
  4. Column assignment:
    • Left child: column - 1
    • Right child: column + 1
  5. Grouping: Add node values to their respective columns
  6. Result construction: Convert map to result vector in sorted column order

Example Walkthrough:

For root = [3,9,20,null,null,15,7]:

Tree structure:
    3
   / \
  9   20
     /  \
    15   7

Column assignment:
    3 (col=0)
   / \
  9   20
(col=-1) (col=1)
     /  \
    15   7
(col=0) (col=2)

BFS Process:
Level 0: [(3,0)] → map[0] = [3]
Level 1: [(9,-1), (20,1)] → map[-1] = [9], map[1] = [20]
Level 2: [(15,0), (7,2)] → map[0] = [3,15], map[2] = [7]

Final map: {-1: [9], 0: [3,15], 1: [20], 2: [7]}
Result: [[9], [3,15], [20], [7]]

Time Complexity: O(n log n)

  • BFS traversal: O(n) - visit each node once
  • Map operations: O(log n) per insertion (map is sorted)
  • Total: O(n log n)

Space Complexity: O(n)

  • Queue: O(n) - maximum width of tree
  • Map: O(n) - stores all node values
  • Result: O(n) - output vector
  • Total: O(n)

    Key Points

  1. BFS for level order: Maintains top-to-bottom order within columns
  2. Column tracking: Use integer column indices for grouping
  3. Map for grouping: Automatically sorts columns from left to right
  4. Level-by-level processing: Ensures proper ordering within columns
  5. Edge case handling: Return empty vector for null root

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Tree, BFS, Vertical Order, Level Order, Medium

Key Takeaways

  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.

References

Template Reference