Vertical Order Traversal of a Binary Tree

Vertical Order Traversal of a Binary Tree - Problem

Vertical Order Traversal of a Binary Tree

Imagine viewing a binary tree from above and projecting all nodes onto a 2D grid. Each node occupies a position (row, col) where the root starts at (0, 0). When you move to a left child, you go one row down and one column left: (row + 1, col - 1). For a right child, you go one row down and one column right: (row + 1, col + 1).

Your task is to return the vertical order traversal - a list of node values grouped by column, ordered from leftmost to rightmost column. Within each column, nodes should be ordered from top to bottom by row. If multiple nodes share the same (row, col) position, sort them by their values in ascending order.

Goal: Return a 2D list where each inner list contains all node values in a specific column, ordered correctly.

Input: Root of a binary tree
Output: List of lists representing vertical order traversal

Input & Output

example_1.py — Basic Tree

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

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

💡 Note: Root at (0,0), left child 9 at (-1,1), right child 20 at (1,1). Node 20 has children 15 at (0,2) and 7 at (2,2). Column -1: [9], Column 0: [3,15] (3 comes before 15 by row), Column 1: [20], Column 2: [7].

example_2.py — Same Position Nodes

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

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

💡 Note: Multiple nodes can have same (row,col). Node 1 at (0,0), nodes 5 and 6 both at (2,0). When nodes share position, sort by value: [1,5,6] not [1,6,5].

example_3.py — Single Node

$ Input: root = [1]

› Output: [[1]]

💡 Note: Single node at (0,0) forms one column with one element.

Constraints

The number of nodes in the tree is in the range [1, 1000]
-1000 ≤ Node.val ≤ 1000
All node values are unique (except for duplicate position sorting test cases)

Asked in

The optimal approach uses a hash map to group nodes by column during a single DFS traversal. Each column stores (row, value) pairs which are sorted before building the final result. This achieves O(n log(n/w)) time complexity where w is the tree width, significantly better than the brute force O(n²w) approach.

Common Approaches

Approach	Time	Space	Notes
✓ One-Pass Hash Table (Optimal)	O(n log(n/w))	O(n)	Use hash map to directly group nodes by column during single traversal
Two-Pass Hash Table	O(n log n)	O(n)	Collect all nodes with coordinates first, then organize by columns
Brute Force (Multiple Tree Traversals)	O(n² * w)	O(n)	Find column range first, then traverse tree multiple times for each column

One-Pass Hash Table (Optimal) — Algorithm Steps

Create hash map with column index as key
Single DFS traversal: for each node, add (row, val) to map[col]
Track minimum and maximum column indices during traversal
For each column from min to max, sort its nodes by row then value
Collect sorted values from each column into final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Hash Map

Create map where keys are column indices, values are node lists

Single DFS Traversal

For each node, immediately add (row, val) to map[column]

Sort Each Column

Sort nodes within each column by row then value

Build Result

Collect values from columns in left-to-right order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct NodeInfo {
    int row, val;
};

struct ColumnData {
    int col;
    struct NodeInfo* nodes;
    int size;
    int capacity;
};

struct ColumnData columns[20000];
int colCount = 0;
int minCol = INT_MAX, maxCol = INT_MIN;

int findOrCreateColumn(int col) {
    for (int i = 0; i < colCount; i++) {
        if (columns[i].col == col) return i;
    }
    
    columns[colCount].col = col;
    columns[colCount].nodes = malloc(1000 * sizeof(struct NodeInfo));
    columns[colCount].size = 0;
    columns[colCount].capacity = 1000;
    return colCount++;
}

void dfs(struct TreeNode* node, int row, int col) {
    if (!node) return;
    
    int idx = findOrCreateColumn(col);
    
    if (columns[idx].size >= columns[idx].capacity) {
        columns[idx].capacity *= 2;
        columns[idx].nodes = realloc(columns[idx].nodes, columns[idx].capacity * sizeof(struct NodeInfo));
    }
    
    columns[idx].nodes[columns[idx].size].row = row;
    columns[idx].nodes[columns[idx].size].val = node->val;
    columns[idx].size++;
    
    if (col < minCol) minCol = col;
    if (col > maxCol) maxCol = col;
    
    dfs(node->left, row + 1, col - 1);
    dfs(node->right, row + 1, col + 1);
}

int compareNodes(const void* a, const void* b) {
    struct NodeInfo* na = (struct NodeInfo*)a;
    struct NodeInfo* nb = (struct NodeInfo*)b;
    
    if (na->row != nb->row) return na->row - nb->row;
    return na->val - nb->val;
}

int compareColumns(const void* a, const void* b) {
    struct ColumnData* ca = (struct ColumnData*)a;
    struct ColumnData* cb = (struct ColumnData*)b;
    return ca->col - cb->col;
}

int** verticalTraversal(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    colCount = 0;
    minCol = INT_MAX;
    maxCol = INT_MIN;
    
    dfs(root, 0, 0);
    
    // Sort columns by column index
    qsort(columns, colCount, sizeof(struct ColumnData), compareColumns);
    
    *returnSize = colCount;
    int** result = malloc(colCount * sizeof(int*));
    *returnColumnSizes = malloc(colCount * sizeof(int));
    
    for (int i = 0; i < colCount; i++) {
        qsort(columns[i].nodes, columns[i].size, sizeof(struct NodeInfo), compareNodes);
        
        result[i] = malloc(columns[i].size * sizeof(int));
        (*returnColumnSizes)[i] = columns[i].size;
        
        for (int j = 0; j < columns[i].size; j++) {
            result[i][j] = columns[i].nodes[j].val;
        }
        
        free(columns[i].nodes);
    }
    
    return result;
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(n/w))

Single traversal O(n) + sorting within each column. Total sorting is O(n log(n/w)) where w is width, since nodes are distributed across columns

⚡ Linearithmic

Space Complexity

O(n)

Hash map storing all nodes grouped by column plus recursion stack

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen