Top View of Binary Tree in DSA C++ - Time & Space Complexity

Time Complexity: Top View of Binary Tree

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find the top view of a binary tree changes as the tree grows.

How does the number of nodes affect the work done to get the top view?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Function to print top view of binary tree
void topView(Node* root) {
    if (!root) return;
    map topNode;
    queue> q;
    q.push({root, 0});

    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* node = p.first;
        int hd = p.second;

        if (topNode.find(hd) == topNode.end())
            topNode[hd] = node->data;

        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }

    for (auto it : topNode)
        cout << it.second << " ";
}
    

This code uses a breadth-first search (BFS) to visit nodes level by level and records the first node encountered at each horizontal distance (hd) using a map.

Identify Repeating Operations

• Primary loop: BFS while loop visits each of the n nodes exactly once.
• Per-node operations: Queue pop (O(1)), map find (O(log w), where w is current map size ≤ n), conditional insert (O(log n) at most once per unique hd).
• Key insight: Map operations (find/insert) occur for every node, not just unique hd.

How Execution Grows With Input

The BFS visits n nodes, but each visit includes O(log n) map work. Total work: O(n log n). Printing traverses the map once: O(w) where w ≤ n (negligible).

Input Size (n)	Approx. Operations
10	About 10 * log(10) ≈ 30 map ops + queue work
100	About 100 * log(100) ≈ 700 map ops
1000	About 1000 * log(1000) ≈ 10,000 map ops

Pattern observation: Grows as n log n, faster than linear due to map lookups per node.

Final Time Complexity

Time Complexity: O(n log n)

Dominated by n map operations, each O(log n). Space: O(w) for map + O(w) queue, worst O(n).

Common Mistake

[X] Wrong: "Visits each node once, map only inserts unique hd (≤ n), so O(n)."

[OK] Correct: Map find runs for every node (n times), each O(log n), even if insert skipped. Total: O(n log n).

Interview Connect

Spotting the hidden log n from map usage per node distinguishes solid analysis. Optimize with unordered_map (avg O(n)) or vertical order traversal tweaks.

Self-Check

"What if we used unordered_map instead of map? How would the time complexity change in average/worst case?"