Top View of Binary Tree in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the Top View of a binary tree represent?

The top view of a binary tree shows the nodes visible when the tree is seen from above. It includes the first node at each horizontal distance from the root.

beginner

How is the horizontal distance of nodes defined in the top view of a binary tree?

Horizontal distance is measured from the root node: root has distance 0, left child decreases distance by 1, right child increases distance by 1.

intermediate

Which data structure is commonly used to track nodes and their horizontal distances in top view calculation?

A queue is used for level order traversal, and a dictionary (or map) stores the first node encountered at each horizontal distance.

beginner

Why do we only keep the first node encountered at each horizontal distance in the top view?

Because the first node at a horizontal distance is the one visible from the top; nodes below it are hidden behind.

intermediate

What is the time complexity of finding the top view of a binary tree using level order traversal?

The time complexity is O(n), where n is the number of nodes, since each node is visited once.

What data structure helps track nodes by their horizontal distance in top view?

A Stack

B Dictionary or Map

C Linked List

D Array

A dictionary or map stores the first node at each horizontal distance for quick lookup.

In top view, what horizontal distance does the root node have?

A 0

B 1

C -1

D Depends on tree height

The root node is assigned horizontal distance 0 by definition.

Which traversal method is best suited for computing the top view?

A Level order traversal

B Inorder traversal

C Preorder traversal

D Postorder traversal

Level order traversal visits nodes level by level, helping identify the first node at each horizontal distance.

If two nodes share the same horizontal distance, which one appears in the top view?

A The rightmost node

B The one at the lower level

C The one at the higher level (closer to root)

D The leftmost node

The top view shows the node closest to the root at each horizontal distance.

What is the output of top view for a tree with nodes 1 (root), 2 (left child), 3 (right child)?

A 3 -> 1 -> 2

B 1 -> 2 -> 3

C 1 only

D 2 -> 1 -> 3

Nodes 2, 1, and 3 are visible from top in order of their horizontal distances: -1, 0, 1.

Explain how to find the top view of a binary tree step-by-step.

Think about how to visit nodes and remember which ones are visible from above.

Why do we use a dictionary/map and a queue together to find the top view?

Consider how to visit nodes in order and remember the first visible node at each position.

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