Vertical Order Traversal of Binary Tree in DSA Typescript

Mental Model

We group tree nodes by their vertical columns from left to right, collecting nodes that share the same horizontal distance from the root.

Analogy: Imagine standing in front of a tall building and looking straight at it. You see windows stacked vertically in columns. Vertical order traversal is like listing all windows column by column from left to right.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns:
-2    -1    0     1     2
 4  ->  2  ->  1,5  ->  3  ->  6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print nodes grouped by vertical columns from left to right, top to bottom within each column.

Step 1: Start at root node 1 with column 0

Column 0: [1]

Why: Root is the center column, starting point for vertical indexing

Step 2: Move to left child 2 with column -1

Column -1: [2]
Column 0: [1]

Why: Left child is one column to the left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Column -1: [2]
Column 0: [1]

Why: Left child again moves one column left

Step 4: Back to 2, move to right child 5 with column 0

Column -2: [4]
Column -1: [2]
Column 0: [1,5]

Why: Right child moves one column right from parent

Step 5: Back to root 1, move to right child 3 with column 1

Column -2: [4]
Column -1: [2]
Column 0: [1,5]
Column 1: [3]

Why: Right child moves one column right

Step 6: Move to right child 6 of 3 with column 2

Column -2: [4]
Column -1: [2]
Column 0: [1,5]
Column 1: [3]
Column 2: [6]

Why: Right child moves one column right

Result:

4 -> 2 -> 1 -> 5 -> 3 -> 6

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function verticalOrderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const columnTable = new Map<number, number[]>();
  const queue: Array<[TreeNode, number]> = [[root, 0]];
  let minColumn = 0, maxColumn = 0;

  while (queue.length > 0) {
    const [node, column] = queue.shift()!;
    if (!columnTable.has(column)) {
      columnTable.set(column, []);
    }
    columnTable.get(column)!.push(node.val);

    if (node.left) {
      queue.push([node.left, column - 1]);
      minColumn = Math.min(minColumn, column - 1);
    }
    if (node.right) {
      queue.push([node.right, column + 1]);
      maxColumn = Math.max(maxColumn, column + 1);
    }
  }

  const result: number[] = [];
  for (let col = minColumn; col <= maxColumn; col++) {
    if (columnTable.has(col)) {
      result.push(...columnTable.get(col)!);
    }
  }
  return result;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
);

const output = verticalOrderTraversal(root);
console.log(output.join(' -> '));

const queue: Array<[TreeNode, number]> = [[root, 0]];

Initialize queue with root node at column 0

const [node, column] = queue.shift()!;

Dequeue node and its column for processing

if (!columnTable.has(column)) { columnTable.set(column, []); }

Create list for column if not exists

columnTable.get(column)!.push(node.val);

Add current node value to its column list

if (node.left) { queue.push([node.left, column - 1]); minColumn = Math.min(minColumn, column - 1); }

Add left child with column one less, update min column

if (node.right) { queue.push([node.right, column + 1]); maxColumn = Math.max(maxColumn, column + 1); }

Add right child with column one more, update max column

for (let col = minColumn; col <= maxColumn; col++) { if (columnTable.has(col)) { result.push(...columnTable.get(col)!); } }

Collect nodes from leftmost to rightmost column

Output

4 -> 2 -> 1 -> 5 -> 3 -> 6

Complexity Analysis

Time: O(n) because each node is visited once during BFS traversal

Space: O(n) for storing nodes in the queue and the column table

vs Alternative: Compared to DFS, BFS ensures nodes are processed top to bottom per column naturally, avoiding extra sorting

Edge Cases

Empty tree (root is null)

Returns empty list immediately

DSA Typescript

if (!root) return [];

Tree with only root node

Returns list with single root value

DSA Typescript

const queue: Array<[TreeNode, number]> = [[root, 0]];

Tree with multiple nodes in same column

Nodes appear in order of BFS traversal (top to bottom)

DSA Typescript

columnTable.get(column)!.push(node.val);

When to Use This Pattern

When a problem asks to group tree nodes by vertical columns or horizontal distance, use vertical order traversal with BFS and column indexing to capture nodes column-wise.

Common Mistakes

Mistake: Using DFS without tracking node levels causes incorrect top-to-bottom order within columns
Fix: Use BFS to process nodes level by level ensuring correct vertical order

Mistake: Not tracking min and max column indices leads to unordered output
Fix: Track minColumn and maxColumn during traversal to output columns left to right

Summary

Groups binary tree nodes by their vertical columns from left to right, preserving top-to-bottom order within each column.

Use when you need to print or process nodes column-wise in a binary tree.

The key insight is to assign a column index to each node and use BFS to maintain top-to-bottom order.