Vertical Order Traversal of Binary Tree in DSA C++ - 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 changes as the tree grows.

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.

struct Node {
  int data;
  Node* left;
  Node* right;
};

void verticalOrder(Node* root) {
  map<int, vector<int>> nodes;
  queue<pair<Node*, int>> q;
  q.push({root, 0});
  while (!q.empty()) {
    auto [node, hd] = q.front(); q.pop();
    nodes[hd].push_back(node->data);
    if (node->left) q.push({node->left, hd - 1});
    if (node->right) q.push({node->right, hd + 1});
  }
}
    

This code visits each node once, grouping nodes by their horizontal distance (hd) from the root.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: Exactly once per node, so n times for n nodes.

How Execution Grows With Input

As the number of nodes grows, the work grows roughly the same amount.

Input Size (n)	Approx. Operations
10	About 10 visits and insertions
100	About 100 visits and insertions
1000	About 1000 visits and insertions

Pattern observation: The operations grow linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit more than linearly because of sorting keys in the map, but mostly it depends on the number of nodes.

Common Mistake

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

[OK] Correct: The map stores nodes by horizontal distance and keeps keys sorted, so inserting each node involves a log n cost, making total time O(n log n).

Interview Connect

Understanding this complexity helps you explain how tree traversals combined with data structures like maps affect performance, a common topic in interviews.

Self-Check

"What if we used an unordered_map instead of map? How would the time complexity change?"