Binary Tree Vertical Order Traversal

Medium · Graphs · Explanation and code example

Depth First Search (Optimal)

How it works

Similar to the optimal BFS approach, we track min and max column indices during DFS to avoid sorting columns. However, we still need to store row information and sort within each column since DFS doesn't visit nodes in level order. This approach reduces the complexity of iterating over columns while still requiring per-column sorting.

Steps

  1. Use a hash map to store (row, value) pairs for each column.
  2. Track minCol and maxCol column indices during traversal.
  3. Define a dfs function that updates minCol/maxCol and adds (row, value) to the column list.
  4. Recursively traverse left and right children with updated row and column values.
  5. After dfs completes, iterate from minCol to maxCol.
  6. For each column, sort entries by row and extract the values.

Complexity

  • Time complexity: O(w * h log h)
  • Space complexity: O(n)

Where n is the number of nodes, h is the height of the tree (i.e. maximum number of nodes in any vertical line of the tree), and w is the width of the tree (i.e. maximum number of nodes in any of the levels of the tree).

Things to watch for

Using DFS Without Tracking Row Index

DFS does not visit nodes level by level, so nodes in the same column may be visited out of order. Without storing the row index alongside each value, nodes at the same column will appear in traversal order rather than top-to-bottom order, violating the problem's requirement.

Forgetting to Handle the Left-Before-Right Ordering

When two nodes share the same row and column (which can happen with certain tree structures), the node that appears first from left to right in the tree should come first in the result. BFS naturally handles this, but DFS with unstable sorting can break this ordering.

Sorting Columns Instead of Tracking Min/Max

Sorting all column keys at the end works but is less efficient. A common mistake is not realizing that column indices are consecutive integers from minCol to maxCol, allowing direct iteration without sorting.

Python code example

from typing import List, Optional
from collections import defaultdict

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        cols = defaultdict(list)
        minCol = maxCol = 0

        def dfs(node, row, col):
            nonlocal minCol, maxCol
            if not node:
                return
            cols[col].append((row, node.val))
            minCol = min(minCol, col)
            maxCol = max(maxCol, col)
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        res = []
        for c in range(minCol, maxCol + 1):
            # sort by row only
            col_vals = sorted(cols[c], key=lambda x: x[0])
            res.append([val for _, val in col_vals])
        return res

C++ code example

/**
 * 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 {
    unordered_map<int, vector<pair<int, int>>> cols;
    int minCol = 0, maxCol = 0;

    void dfs(TreeNode* node, int row, int col) {
        if (!node) return;
        cols[col].emplace_back(row, node->val);
        minCol = min(minCol, col);
        maxCol = max(maxCol, col);
        dfs(node->left, row + 1, col - 1);
        dfs(node->right, row + 1, col + 1);
    }

public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        dfs(root, 0, 0);
        vector<vector<int>> res;

        for (int c = minCol; c <= maxCol; ++c) {
            auto& vec = cols[c];
            stable_sort(vec.begin(), vec.end(),
                        [](const pair<int, int>& a, const pair<int, int>& b) {
                            return a.first < b.first; // sort by row only
                        });
            vector<int> colVals;
            for (auto& [_, val] : vec)
                colVals.push_back(val);
            res.push_back(colVals);
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations