Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Vertical Order Traversal of a Binary Tree

HARDProblemSolveExternal Links

Description

You are given the root of a binary tree. Your task is to compute its vertical order traversal.

Imagine the tree placed on a 2D grid. The root sits at position (row = 0, col = 0). For any node located at (row, col), its left child occupies (row + 1, col - 1) and its right child occupies (row + 1, col + 1).

The vertical order traversal is a list of groups, one group per column, ordered from the leftmost column to the rightmost column. Within each column, nodes are ordered from top to bottom (by row). If two or more nodes share the exact same (row, col) position, they are sorted by their values in ascending order.

Return the vertical order traversal as a list of lists of node values.

Examples

Example 1

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

        3
       / \
      9   20
         /  \
        15    7

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

Explanation:

  • Column -1: Node 9 is the only node here.
  • Column 0: Node 3 is at row 0 and node 15 is at row 2. Top-to-bottom order gives [3, 15].
  • Column 1: Node 20 is the only node here.
  • Column 2: Node 7 is the only node here.

Example 2

Input: root = [1, 2, 3, 4, 5, 6, 7]

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Output: [[4], [2], [1, 5, 6], [3], [7]]

Explanation:

  • Column -2: Node 4.
  • Column -1: Node 2.
  • Column 0: Nodes 1 (row 0), 5 (row 2), and 6 (row 2). Node 1 comes first because it has a smaller row. Nodes 5 and 6 share position (row 2, col 0), so they are sorted by value: 5 before 6.
  • Column 1: Node 3.
  • Column 2: Node 7.

Example 3

Input: root = [1, 2, 3, 4, 6, 5, 7]

        1
       / \
      2   3
     / \ / \
    4  6 5  7

Output: [[4], [2], [1, 5, 6], [3], [7]]

Explanation: This tree is identical to Example 2 except nodes 5 and 6 are swapped. However, both still land at position (row 2, col 0). Since same-position nodes are sorted by value, the result is the same: 5 appears before 6.

Constraints

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

Editorial

Brute Force - DFS with Global Sort

Intuition

The most direct way to think about this problem is to imagine pinning the tree onto a 2D grid. Every node gets a coordinate (row, col). The root starts at (0, 0). Each time you move to a left child, the column decreases by 1 and the row increases by 1. Each time you move to a right child, the column increases by 1 and the row increases by 1.

Once every node has a coordinate, the rest is just sorting. We need the output grouped by column (left to right), and within each column sorted by row (top to bottom), and for nodes sharing the exact same position sorted by value.

This naturally leads to a simple plan:

  1. Traverse the entire tree (using DFS) and record each node as a triple (col, row, value).
  2. Sort all the triples — since we sort by column first, then row, then value, a single sort gives us the exact ordering we need.
  3. Walk through the sorted list and group consecutive entries with the same column into one sublist.

Think of it like collecting stamps and writing each stamp's position on its back. After collecting all of them, you sort by position and arrange them into columns.

Binary tree placed on a 2D grid showing row and column coordinates for each node
Binary tree placed on a 2D grid showing row and column coordinates for each node

Step-by-Step Explanation

Let's trace through Example 1 with root = [3, 9, 20, null, null, 15, 7]:

        3
       / \
      9   20
         /  \
        15    7

Step 1: Start at root node 3. Its position is (row=0, col=0). Record the triple (col=0, row=0, val=3) in our list.

Step 2: Move left to node 9. Going left means col decreases by 1. Position: (row=1, col=-1). Record (col=-1, row=1, val=9). Node 9 has no children.

Step 3: Backtrack to root node 3. The left subtree is fully explored.

Step 4: Move right to node 20. Going right means col increases by 1. Position: (row=1, col=1). Record (col=1, row=1, val=20). Now explore its children.

Step 5: Move left to node 15. Position: (row=2, col=0). Record (col=0, row=2, val=15). Notice the column returns to 0 — going right then left from root cancels out: 0 + 1 - 1 = 0.

Step 6: Backtrack to node 20, then move right to node 7. Position: (row=2, col=2). Record (col=2, row=2, val=7). All nodes are now visited.

Step 7: Sort all 5 records by (col, row, val): (-1,1,9), (0,0,3), (0,2,15), (1,1,20), (2,2,7). Sorting first by column puts col -1 first, then col 0 entries (row 0 before row 2), then col 1, then col 2.

Step 8: Group by column to form the result: col -1 → [9], col 0 → [3, 15], col 1 → [20], col 2 → [7]. Final answer: [[9], [3, 15], [20], [7]].

DFS Traversal with Position Recording — Watch how DFS explores the tree while recording each node's column, row, and value, then sorts and groups the records into the final vertical order.

Algorithm

  1. Create an empty list records to store (col, row, value) triples.
  2. Perform DFS starting from the root at (row=0, col=0):
    • For each non-null node, append (col, row, node.val) to records.
    • Recurse on the left child with (row+1, col-1).
    • Recurse on the right child with (row+1, col+1).
  3. Sort records — the default tuple comparison sorts by col first, then row, then value.
  4. Walk through the sorted list and group consecutive entries with the same column into one sublist.
  5. Return the list of sublists.

Code

#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> records;
        dfs(root, 0, 0, records);
        sort(records.begin(), records.end());

        vector<vector<int>> result;
        int prevCol = INT_MIN;
        for (auto& [col, row, val] : records) {
            if (col != prevCol) {
                result.push_back({});
                prevCol = col;
            }
            result.back().push_back(val);
        }
        return result;
    }

private:
    void dfs(TreeNode* node, int row, int col,
             vector<tuple<int, int, int>>& records) {
        if (!node) return;
        records.emplace_back(col, row, node->val);
        dfs(node->left, row + 1, col - 1, records);
        dfs(node->right, row + 1, col + 1, records);
    }
};
from typing import Optional, List

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        records = []

        def dfs(node, row, col):
            if not node:
                return
            records.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)
        records.sort()

        result = []
        prev_col = -2000
        for col, row, val in records:
            if col != prev_col:
                result.append([])
                prev_col = col
            result[-1].append(val)

        return result
import java.util.*;

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

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        records.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>> result = new ArrayList<>();
        int prevCol = Integer.MIN_VALUE;
        for (int[] rec : records) {
            if (rec[0] != prevCol) {
                result.add(new ArrayList<>());
                prevCol = rec[0];
            }
            result.get(result.size() - 1).add(rec[2]);
        }
        return result;
    }

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

Complexity Analysis

Time Complexity: O(n log n)

The DFS traversal visits each of the n nodes exactly once, taking O(n) time. Sorting the n records dominates at O(n log n). The final grouping pass is O(n). Total: O(n log n).

Space Complexity: O(n)

We store one triple per node in the records list, using O(n) space. The DFS recursion stack uses O(h) space where h is the tree height (up to O(n) for a skewed tree). The output list also holds all n values. Total: O(n).

Why This Approach Is Not Efficient

The DFS with global sort approach works correctly and produces the right answer in O(n log n) time. However, it has several conceptual drawbacks:

1. The entire tree must be traversed before any grouping can begin. All node positions are dumped into a flat list. No structure is imposed until the sort runs. If the tree is very large, we collect thousands of records before we even know how many columns exist.

2. The sort treats all columns as one problem. Records from column -10 and column +10 are compared against each other during sorting, even though they will never appear in the same output group. The sort does unnecessary cross-column comparisons.

3. DFS ignores the tree's natural level structure. The problem requires row-based ordering within each column, but DFS visits nodes in a path-based order. We recover the correct row order only because we explicitly recorded it and sorted by it. A level-order traversal (BFS) naturally processes nodes row by row, giving us row ordering for free.

Key insight: Instead of collecting everything into a flat list and sorting globally, we can organize data into columns as we traverse. A sorted map keyed by column number — where each column stores entries sorted by (row, value) — achieves this. BFS makes the level ordering automatic, and a sorted map keeps columns ordered without a separate sort step.

Optimal Approach - BFS with Ordered Map

Intuition

Instead of collecting all data and sorting it after the fact, we can organize nodes into the right structure as we traverse the tree.

The idea is to use BFS (level-order traversal) combined with an ordered map (TreeMap in Java, map in C++, or a sorted dictionary in Python). BFS processes nodes level by level, which means all nodes at row 0 are processed before row 1, which are processed before row 2. This gives us the top-to-bottom ordering within each column automatically.

As we dequeue each node, we insert it into a map keyed by its column number. Within each column, we use another sorted structure keyed by row number. For nodes sharing the exact same (row, col) position, we use a sorted collection (like a priority queue or multiset) to keep values in ascending order.

The result is built by iterating through the map's keys in order (leftmost column first) and collecting the values within each column.

Think of it like a librarian organizing books into labeled shelves (columns) as they arrive, rather than dumping all books on the floor and sorting them afterward.

Step-by-Step Explanation

Let's trace Example 2 with root = [1, 2, 3, 4, 5, 6, 7] to see the BFS approach handle the same-position case:

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Step 1: Initialize BFS queue with root node 1 at (row=0, col=0). The column map is empty.

Step 2: Dequeue node 1 at (row=0, col=0). Insert into column_map[0]. Enqueue its children: node 2 (row=1, col=-1) and node 3 (row=1, col=1).

  • Map: {0: [(row=0, val=1)]}

Step 3: Dequeue node 2 at (row=1, col=-1). Insert into column_map[-1]. Enqueue children: node 4 (row=2, col=-2) and node 5 (row=2, col=0).

  • Map: {0: [(0,1)], -1: [(1,2)]}

Step 4: Dequeue node 3 at (row=1, col=1). Insert into column_map[1]. Enqueue children: node 6 (row=2, col=0) and node 7 (row=2, col=2).

  • Map: {0: [(0,1)], -1: [(1,2)], 1: [(1,3)]}

Step 5: Dequeue node 4 at (row=2, col=-2). Insert into column_map[-2]. Leaf node — no children.

  • Map: {-2: [(2,4)], 0: [(0,1)], -1: [(1,2)], 1: [(1,3)]}

Step 6: Dequeue node 5 at (row=2, col=0). Insert into column_map[0]. Column 0 now has two entries.

  • Map: {-2: [(2,4)], -1: [(1,2)], 0: [(0,1), (2,5)], 1: [(1,3)]}

Step 7: Dequeue node 6 at (row=2, col=0). Same position as node 5! Both at (row=2, col=0). Insert into column_map[0]. When we later sort within this column, nodes 5 and 6 will be ordered by value: 5 before 6.

  • Map: {-2: [(2,4)], -1: [(1,2)], 0: [(0,1), (2,5), (2,6)], 1: [(1,3)]}

Step 8: Dequeue node 7 at (row=2, col=2). Insert into column_map[2]. Queue is now empty — BFS complete.

  • Map: {-2: [(2,4)], -1: [(1,2)], 0: [(0,1), (2,5), (2,6)], 1: [(1,3)], 2: [(2,7)]}

Step 9: Iterate through columns in sorted order (-2, -1, 0, 1, 2). For column 0, sort entries by (row, value): node 1 (row 0) first, then nodes 5 and 6 (row 2) sorted by value → [1, 5, 6]. Final result: [[4], [2], [1, 5, 6], [3], [7]].

BFS Level-Order with Column Mapping — Watch how BFS processes nodes level by level, inserting each into a sorted column map, and correctly handling nodes 5 and 6 that share the same position.

Algorithm

  1. Create an ordered map: column → (sorted by row → sorted values).
    • In Java: TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>>
    • In C++: map<int, map<int, multiset<int>>>
    • In Python: defaultdict(list) with later sorting per column
  2. Initialize a BFS queue with (root, row=0, col=0).
  3. While the queue is not empty:
    • Dequeue (node, row, col).
    • Insert node.val into the map at [col][row].
    • If node.left exists, enqueue (node.left, row+1, col-1).
    • If node.right exists, enqueue (node.right, row+1, col+1).
  4. Iterate through the map's columns in sorted order.
    • For each column, iterate through rows in sorted order.
    • Collect values (already sorted within same position) into a sublist.
  5. Return the list of sublists.

Code

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

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        // column -> row -> sorted values
        map<int, map<int, multiset<int>>> columnMap;
        queue<pair<TreeNode*, pair<int, int>>> q;
        q.push({root, {0, 0}});

        while (!q.empty()) {
            auto [node, pos] = q.front();
            q.pop();
            auto [row, col] = pos;

            columnMap[col][row].insert(node->val);

            if (node->left)
                q.push({node->left, {row + 1, col - 1}});
            if (node->right)
                q.push({node->right, {row + 1, col + 1}});
        }

        vector<vector<int>> result;
        for (auto& [col, rows] : columnMap) {
            vector<int> column;
            for (auto& [row, vals] : rows) {
                column.insert(column.end(), vals.begin(), vals.end());
            }
            result.push_back(column);
        }
        return result;
    }
};
from collections import defaultdict, deque
from typing import Optional, List

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        column_map = defaultdict(list)
        queue = deque([(root, 0, 0)])  # (node, row, col)

        while queue:
            node, row, col = queue.popleft()
            column_map[col].append((row, node.val))

            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        result = []
        for col in sorted(column_map.keys()):
            # Sort by row first, then by value for same-position nodes
            column = [val for row, val in sorted(column_map[col])]
            result.append(column)

        return result
import java.util.*;

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // column -> row -> sorted values
        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0, 0});

        while (!queue.isEmpty()) {
            Object[] curr = queue.poll();
            TreeNode node = (TreeNode) curr[0];
            int row = (int) curr[1];
            int col = (int) curr[2];

            map.computeIfAbsent(col, k -> new TreeMap<>())
               .computeIfAbsent(row, k -> new PriorityQueue<>())
               .offer(node.val);

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

        List<List<Integer>> result = new ArrayList<>();
        for (TreeMap<Integer, PriorityQueue<Integer>> rows : map.values()) {
            List<Integer> column = new ArrayList<>();
            for (PriorityQueue<Integer> vals : rows.values()) {
                while (!vals.isEmpty()) {
                    column.add(vals.poll());
                }
            }
            result.add(column);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

BFS visits each of the n nodes once in O(n). Inserting into a TreeMap (C++ map / Java TreeMap) takes O(log n) per insertion, giving O(n log n) total for all insertions. Extracting results also takes O(n) in total. In the Python version, sorting each column's entries at the end contributes O(n log n) in the worst case. Overall: O(n log n).

Space Complexity: O(n)

The column map stores all n node values, using O(n) space. The BFS queue holds at most O(n) entries (in a perfect binary tree, the last level alone has ~n/2 nodes). The output list stores all n values. Total: O(n).