Vertical Order Traversal of Binary Tree in DSA Typescript - Time & Space Complexity

Time Complexity: Vertical Order Traversal of Binary Tree

O(n + k log k)

Understanding Time Complexity

We want to understand how the time needed to do vertical order traversal grows as the tree gets bigger.

Specifically, how does the number of nodes affect the work done to group nodes by their vertical columns?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map();
  const queue: Array<[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]);
}
    

This code does a breadth-first traversal of the tree, grouping nodes by their vertical column index.

Identify Repeating Operations

• Primary operation: The while loop processes each node exactly once.
• How many times: Once for every node in the tree (n times).
• Inside the loop, adding nodes to the queue and map are constant time operations.
• Sorting the map entries happens once after traversal, based on the number of unique columns.

How Execution Grows With Input

As the number of nodes (n) grows, the traversal work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 steps to visit nodes + sorting few columns
100	About 100 steps to visit nodes + sorting columns
1000	About 1000 steps to visit nodes + sorting columns

Pattern observation: The main work grows linearly with the number of nodes, while sorting columns depends on tree width but is usually much smaller.

Final Time Complexity

Time Complexity: O(n + k log k)

This means the time grows mostly with the number of nodes, plus a smaller cost to sort the vertical columns, where k is the number of columns.

Common Mistake

[X] Wrong: "The sorting step dominates and makes this O(n log n)."

[OK] Correct: The sorting is done on the number of columns, which is at most n but usually much smaller, so the main cost is still visiting each node once.

Interview Connect

Understanding this complexity helps you explain how tree traversals scale and how extra steps like sorting affect performance, a skill useful in many coding problems.

Self-Check

What if we used a depth-first traversal instead of breadth-first? How would the time complexity change?

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