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?