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

Time Complexity: Vertical Order Traversal of Binary Tree

O(n log n)

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?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function verticalOrder(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [[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 [...map.entries()].sort((a, b) => a[0] - b[0]).map(entry => entry[1]);
}
    

This code does a breadth-first search to group nodes by their vertical column index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop processes each node once.
• How many times: Exactly once per node, so n times if there are n nodes.

How Execution Grows With Input

As the number of nodes grows, the loop runs once for each node.

Input Size (n)	Approx. Operations
10	About 10 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: The work grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n + k log k)

This means the time grows a bit faster than the number of nodes because sorting the columns takes extra time.

Common Mistake

[X] Wrong: "The traversal is just O(n) because we visit each node once."

[OK] Correct: We also sort the column keys at the end, which takes O(k log k) time, where k is the number of columns, making total time O(n + k log k). Since k can be up to n, this is O(n log n).

Interview Connect

Understanding this time complexity helps you explain how traversal and sorting steps combine, showing you can analyze multi-step algorithms clearly.

Self-Check

"What if we used a balanced tree or heap to keep columns sorted during traversal? How would that affect the time complexity?"