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.

Specifically, how does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public IList<int> TopView(TreeNode root) {
    var result = new List<int>();
    if (root == null) return result;

    var queue = new Queue<(TreeNode node, int hd)>();
    var map = new Dictionary<int, int>();
    queue.Enqueue((root, 0));

    while (queue.Count > 0) {
        var (node, hd) = queue.Dequeue();
        if (!map.ContainsKey(hd)) {
            map[hd] = node.val;
        }
        if (node.left != null) queue.Enqueue((node.left, hd - 1));
        if (node.right != null) queue.Enqueue((node.right, hd + 1));
    }

    foreach (var key in map.Keys.OrderBy(k => k)) {
        result.Add(map[key]);
    }
    return result;
}
    

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

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.
• Inside the loop, checking and inserting into the dictionary happens once per node.
• Sorting the keys at the end depends on the number of unique horizontal distances, at most n.

How Execution Grows With Input

As the number of nodes grows, the operations grow roughly the same amount.

Input Size (n)	Approx. Operations
10	About 10 visits + sorting keys (up to 10)
100	About 100 visits + sorting keys (up to 100)
1000	About 1000 visits + sorting keys (up to 1000)

Pattern observation: The work grows linearly with the number of nodes, plus a sorting step that grows a bit faster but still manageable.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of nodes because of sorting the horizontal distances, but still efficient for most trees.

Common Mistake

[X] Wrong: "The time complexity is just O(n) because we visit each node once, so sorting doesn't matter."

[OK] Correct: Sorting the horizontal distances at the end takes extra time, which depends on how many unique distances there are, up to n, so it adds a log n factor.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze both traversal and sorting steps clearly.

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?"

Practice

1. What does the Top View of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the top

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the right side

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree includes all nodes visible when looking down from above the tree.

2. Step 2: Differentiate from other views

   Left or right views show nodes from side angles, while top view shows nodes from above.

3. Final Answer:

   Nodes visible when the tree is viewed from the top -> Option A

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right side views
• Thinking top view includes all leaf nodes
• Assuming top view shows all nodes in the tree

2. Which of the following C# code snippets correctly declares a node class for a binary tree used in top view calculation?

easy

A. public class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } }

B. class Node { int data; Node left, right; Node(int val) { data = val; left = right = null; } }

C. public struct Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } }

D. public class Node { int data; Node left, right; Node() { data = 0; left = right = null; } }

Solution

1. Step 1: Check access modifiers and constructor

   public class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } uses public class, public fields, and a constructor with parameter, which is correct for node definition.

2. Step 2: Identify issues in other options

   class Node { int data; Node left, right; Node(int val) { data = val; left = right = null; } } lacks access modifiers (default private), public struct Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } uses struct which is not typical for tree nodes, public class Node { int data; Node left, right; Node() { data = 0; left = right = null; } } lacks constructor parameter and fields are private.

3. Final Answer:

   public class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } -> Option A

4. Quick Check:

   Public class with constructor and public fields = public class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } [OK]

Hint: Use public class with constructor and public fields for nodes [OK]

Common Mistakes:

• Omitting public access modifiers causing inaccessible fields
• Using struct instead of class for nodes
• Not initializing left and right to null

3. Consider the following binary tree:

        1
       / \
      2   3
       \   \
        4   5
         \
          6

What is the top view of this tree?

medium

A. [2, 1, 3, 6]

B. [1, 2, 4, 6, 5]

C. [2, 1, 3, 5]

D. [1, 2, 3, 4, 5, 6]

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root (1) has HD=0, left child (2) HD=-1, right child (3) HD=1, node 4 (right of 2) HD=0, node 5 (right of 3) HD=2, node 6 (right of 4) HD=1.

2. Step 2: Select topmost nodes at each HD

   Using BFS order, first node at each HD: HD -1: 2, HD 0: 1 (4 hidden below), HD 1: 3 (6 hidden below), HD 2: 5. Sorted by HD: [2, 1, 3, 5]

3. Final Answer:

   [2, 1, 3, 5] -> Option C

4. Quick Check:

   Top view nodes by HD = [2, 1, 3, 5] [OK]

Hint: Track horizontal distances and pick first node at each HD [OK]

Common Mistakes:

• Ignoring horizontal distances and picking all nodes
• Confusing top view with level order traversal
• Missing nodes with same horizontal distance but different levels

4. The following C# code attempts to print the top view of a binary tree but has a bug. What is the error?

void PrintTopView(Node root) {
  if (root == null) return;
  var map = new Dictionary<int, int>();
  var queue = new Queue<(Node node, int hd)>();
  queue.Enqueue((root, 0));
  while (queue.Count > 0) {
    var (node, hd) = queue.Dequeue();
    map[hd] = node.data;
    if (node.left != null) queue.Enqueue((node.left, hd - 1));
    if (node.right != null) queue.Enqueue((node.right, hd + 1));
  }
  foreach (var key in map.Keys.OrderBy(k => k)) {
    Console.Write(map[key] + " ");
  }
}

medium

A. It does not check for null root

B. It does not enqueue the root node

C. It uses a queue instead of a stack

D. It overwrites nodes at the same horizontal distance instead of keeping the first

Solution

1. Step 1: Analyze map update logic

   The code assigns map[hd] = node.data every time, overwriting previous entries at the same horizontal distance.

2. Step 2: Understand top view requirement

   Top view requires the first node encountered at each horizontal distance, so overwriting causes incorrect output.

3. Final Answer:

   It overwrites nodes at the same horizontal distance instead of keeping the first -> Option D

4. Quick Check:

   Keep first node per HD, not overwrite [OK]

Hint: Store node only if HD not already in map [OK]

Common Mistakes:

• Overwriting map entries for horizontal distances
• Ignoring null root check (though present here)
• Confusing queue with stack usage

5. You want to find the top view of a binary tree but only have access to its inorder and level order traversals:

Inorder: [4, 2, 5, 1, 6, 3, 7]
Level order: [1, 2, 3, 4, 5, 6, 7]

Which approach is best to find the top view?

hard

A. Use level order traversal directly to get top view

B. Reconstruct the tree from traversals, then perform top view traversal

C. Use inorder traversal directly to get top view

D. Top view cannot be found from these traversals

Solution

1. Step 1: Understand traversal information

   Inorder and level order traversals can be used together to reconstruct the binary tree uniquely.

2. Step 2: Apply top view after reconstruction

   Once the tree is rebuilt, perform a top view traversal using horizontal distances and BFS.

3. Final Answer:

   Reconstruct the tree from traversals, then perform top view traversal -> Option B

4. Quick Check:

   Rebuild tree first, then find top view [OK]

Hint: Rebuild tree from traversals before top view [OK]

Common Mistakes:

• Trying to get top view directly from inorder or level order
• Assuming top view is same as level order
• Believing top view cannot be found from given traversals