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.

Practice

1. What does Vertical Order Traversal of a binary tree mean?

easy

A. Nodes are grouped by their vertical columns from left to right

B. Nodes are visited level by level from top to bottom

C. Nodes are visited in preorder (root, left, right)

D. Nodes are visited in inorder (left, root, right)

Solution

1. Step 1: Understand vertical columns in a tree

   Vertical order groups nodes by their horizontal distance from the root, called columns.

2. Step 2: Define vertical order traversal

   Nodes in the same vertical column are collected and output from leftmost to rightmost column.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option A

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns from left to right, not levels or preorder [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Ignoring horizontal distance concept

2. Which TypeScript data structure is best to store nodes by their vertical column during vertical order traversal?

easy

A. Map

B. Set<number>

C. Array<number>

D. string[]

Solution

1. Step 1: Identify need to map columns to nodes

   We need to store nodes grouped by their column index, so a mapping from column number to list of nodes is required.

2. Step 2: Choose appropriate TypeScript structure

   A Map with keys as column numbers and values as arrays of node values fits perfectly.

3. Final Answer:

   Map<number, number[]> -> Option A

4. Quick Check:

   Map column to node list = Map<number, number[]> [OK]

Hint: Use Map to link column numbers to node arrays [OK]

Common Mistakes:

• Using Set which does not store duplicates or order
• Using plain arrays without column keys
• Using string arrays which don't map columns

3. Given this TypeScript code for vertical order traversal, what is the output?

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map();
  const queue: [TreeNode, number][] = [[root, 0]];
  while (queue.length) {
    const [node, col] = queue.shift()!;
    if (!map.has(col)) map.set(col, []);
    map.get(col)!.push(node.val);
    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }
  return Array.from(map.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

console.log(verticalOrder(root));

medium

A. [[7], [3], [1, 5, 6], [2], [4]]

B. [[4], [2], [1, 5, 6], [3], [7]]

C. [[1], [2, 3], [4, 5, 6, 7]]

D. [[4], [2, 5], [1, 6], [3, 7]]

Solution

1. Step 1: Assign columns to nodes during BFS

   Root (1) at col 0; left child (2) at -1; right child (3) at +1; and so on. Nodes grouped by columns: - -2: 4 - -1: 2 - 0: 1, 5, 6 - 1: 3 - 2: 7

2. Step 2: Sort columns and output node lists

   Sorted columns from left to right: -2, -1, 0, 1, 2. Output arrays accordingly.

3. Final Answer:

   [[4], [2], [1, 5, 6], [3], [7]] -> Option B

4. Quick Check:

   Column grouping matches output D [OK]

Hint: Track column indices during BFS, then sort keys [OK]

Common Mistakes:

• Mixing up column indices for left/right children
• Not sorting columns before output
• Using DFS instead of BFS causing wrong order

4. The following TypeScript code for vertical order traversal has a bug. What is the bug?

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map();
  const queue: [TreeNode, number][] = [[root, 0]];
  while (queue.length) {
    const [node, col] = queue.pop()!;
    if (!map.has(col)) map.set(col, []);
    map.get(col)!.push(node.val);
    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }
  return Array.from(map.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

medium

A. map.get(col) returns undefined

B. Missing check for null root

C. Using queue.pop() causes DFS instead of BFS traversal

D. Sorting map entries is incorrect

Solution

1. Step 1: Identify queue operation used

   The code uses queue.pop(), which removes the last element, making it a stack (DFS) behavior.

2. Step 2: Explain impact on vertical order traversal

   Vertical order requires BFS (level order) to maintain correct node order per column. Using pop() breaks this order.

3. Final Answer:

   Using queue.pop() causes DFS instead of BFS traversal -> Option C

4. Quick Check:

   pop() = DFS, need shift() for BFS [OK]

Hint: Use shift() for BFS queue, not pop() [OK]

Common Mistakes:

• Confusing pop() with shift() in queue
• Ignoring traversal order effect on output
• Assuming map.get always returns array without check

5. You want to modify vertical order traversal to sort nodes within the same column by their row (depth) and then by value ascending. Which approach is best?

hard

A. Traverse tree using DFS only and collect nodes in order

B. Use a Set per column to avoid duplicates

C. Sort nodes globally after traversal ignoring columns

D. Store nodes as tuples (row, value) per column and sort before output

Solution

1. Step 1: Understand sorting requirement within columns

   Nodes in the same column must be sorted first by their row (depth), then by value ascending.

2. Step 2: Choose data structure to store row and value

   Store tuples (row, value) for each node in the column map, then sort these tuples before output.

3. Step 3: Explain why other options fail

   Set ignores duplicates and order; DFS alone doesn't guarantee order; global sort ignores column grouping.

4. Final Answer:

   Store nodes as tuples (row, value) per column and sort before output -> Option D

5. Quick Check:

   Sort by row and value per column = store tuples and sort [OK]

Hint: Keep (row, value) pairs per column, then sort [OK]

Common Mistakes:

• Using Set which loses order and duplicates
• Relying on DFS without tracking rows
• Sorting all nodes ignoring column grouping