Top View of Binary Tree in DSA Typescript - 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.

Specifically, how the number of nodes affects the work done to get the top view.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function topView(root: TreeNode | null): number[] {
  if (!root) return [];
  const queue: Array<[TreeNode, number]> = [[root, 0]];
  const map = new Map<number, number>();

  while (queue.length) {
    const [node, hd] = queue.shift()!;
    if (!map.has(hd)) map.set(hd, node.val);
    if (node.left) queue.push([node.left, hd - 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }

  return Array.from(map.entries())
    .sort((a, b) => a[0] - b[0])
    .map(([, val]) => val);
}
    

This code finds the top view of a binary tree by traversing nodes level by level and tracking horizontal distances.

Identify Repeating Operations

• Primary operation: The while loop processes each node once using a queue.
• How many times: Exactly once per node, so n times for n nodes.
• Additional operations: Sorting the map entries at the end based on horizontal distance.

How Execution Grows With Input

As the number of nodes grows, the while loop runs once per node, so operations grow linearly.

Input Size (n)	Approx. Operations
10	About 10 queue operations + sorting ~ 10 log 10
100	About 100 queue operations + sorting ~ 100 log 100
1000	About 1000 queue operations + sorting ~ 1000 log 1000

Pattern observation: The main traversal grows linearly, but sorting adds a small extra cost growing a bit faster than linear.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of nodes because of the sorting step after visiting all nodes.

Common Mistake

[X] Wrong: "The top view can be found in O(n) time without any sorting."

[OK] Correct: We must sort the horizontal distances to output the top view from left to right, which takes O(k log k) time, where k is the number of unique horizontal distances, often proportional to n.

Interview Connect

Understanding this complexity helps you explain how tree traversal and sorting combine in real problems, showing your grasp of both data structures and algorithm efficiency.

Self-Check

What if we used a balanced tree or a data structure that keeps keys sorted during insertion? How would the time complexity change?