Top View of Binary Tree in DSA C# - Execution Trace

Concept Flow - Top View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

For each node dequeued:

↓

Check if horizontal distance seen before?

↓

Add node to top view

↓

Ignore node

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort nodes by horizontal distance

↓

Print top view nodes

Traverse the tree level by level, track horizontal distances, and record the first node at each horizontal distance to get the top view.

Execution Sample

DSA C#

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

void TopView(Node root) {
  // Implementation
}

This code defines a binary tree node and a method to print the top view of the tree.

Execution Table

Step	Operation	Node Processed (data, hd)	Top View Map (hd: node)	Queue State (data, hd)	Visual State
1	Start with root	(1, 0)	{}	[(1,0)]	Tree: 1 HD=0
2	Dequeue node	(1, 0)	{0:1}	[]	Top view: 1 Queue empty
3	Enqueue left child	(2, -1)	{0:1}	[(2,-1)]	Left child 2 at HD -1
4	Enqueue right child	(3, 1)	{0:1}	[(2,-1),(3,1)]	Right child 3 at HD 1
5	Dequeue node	(2, -1)	{0:1, -1:2}	[(3,1)]	Top view: 2,1
6	Enqueue left child	(4, -2)	{0:1, -1:2}	[(3,1),(4,-2)]	Left child 4 at HD -2
7	Enqueue right child	(5, 0)	{0:1, -1:2}	[(3,1),(4,-2),(5,0)]	Right child 5 at HD 0 (ignored in top view)
8	Dequeue node	(3, 1)	{0:1, -1:2, 1:3}	[(4,-2),(5,0)]	Top view: 2,1,3
9	Dequeue node	(4, -2)	{0:1, -1:2, 1:3, -2:4}	[(5,0)]	Top view: 4,2,1,3
10	Dequeue node	(5, 0)	{0:1, -1:2, 1:3, -2:4}	[]	Node 5 at HD 0 ignored (already present)
11	Queue empty	-	{-2:4, -1:2, 0:1, 1:3}	[]	Final top view nodes: 4,2,1,3

💡 Queue is empty, traversal complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 9	Final
Queue	[(1,0)]	[]	[(3,1)]	[(4,-2),(5,0)]	[(5,0)]	[]
Top View Map	{}	{0:1}	{0:1, -1:2}	{0:1, -1:2, 1:3}	{0:1, -1:2, 1:3, -2:4}	{-2:4, -1:2, 0:1, 1:3}

Key Moments - 3 Insights

Why do we ignore nodes at a horizontal distance already in the top view map?

Because the first node encountered at a horizontal distance is the topmost visible node from above. Later nodes at the same horizontal distance are hidden behind it. See steps 7 and 10 in execution_table where nodes at hd=0 are ignored.

Why do we use horizontal distance and level order traversal together?

Horizontal distance helps identify vertical alignment, and level order ensures we see nodes from top to bottom. This combination guarantees the first node at each horizontal distance is the top view node. Refer to the queue processing in execution_table steps 2-10.

How does the queue store nodes with their horizontal distances?

Each queue element stores a node and its horizontal distance (hd). When we enqueue children, we assign hd-1 for left and hd+1 for right. This is shown in steps 3,4,6,7 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what nodes are currently in the top view map?

A {0:1, -1:2}

B {0:1}

C {-1:2}

D {}

💡 Hint

Check the 'Top View Map' column at step 5 in execution_table.

At which step does the horizontal distance -2 first appear in the top view map?

A Step 7

B Step 6

C Step 9

D Step 10

💡 Hint

Look for when hd -2 is added in the 'Top View Map' column in execution_table.

If the node with data 5 was not ignored at step 10, how would the top view map change?

A It would add hd=0 with node 5 alongside node 1

B It would add hd=0 with node 5, replacing node 1

C It would not change because hd=0 is already present

D It would remove all nodes with hd=0

💡 Hint

Refer to the rule that only the first node at each horizontal distance is kept, see step 10.

Concept Snapshot

Top View of Binary Tree:
- Traverse tree level by level (BFS)
- Track horizontal distance (hd) for each node
- Record first node at each hd
- Ignore later nodes at same hd
- Sort recorded nodes by hd for final top view
- Print nodes in order of hd

Full Transcript

The top view of a binary tree shows nodes visible when looking from above. We start at the root with horizontal distance zero. Using a queue, we traverse the tree level by level. For each node, we check if its horizontal distance is already recorded. If not, we add it to the top view map. We enqueue left and right children with hd-1 and hd+1 respectively. This process continues until the queue is empty. Finally, we sort nodes by horizontal distance and print them. This ensures only the topmost nodes at each vertical line are shown.

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