Top View of Binary Tree in DSA C#

Mental Model

We want to see the nodes visible when looking at the tree from above, ignoring nodes hidden behind others.

Analogy: Imagine standing on a balcony looking straight down at a group of trees; you only see the tops of the trees that are not blocked by others.

       1
      / \
     2   3
      \   \
       4   5
        \   \
         6   7

Top view shows nodes: 2 -> 1 -> 3 -> 5 -> 7

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has right child 4; 4 has right child 6; 3 has right child 5; 5 has right child 7

Goal: Print nodes visible from top view: nodes that appear first at each horizontal distance from root

Step 1: Start BFS from root (1) at horizontal distance (hd) = 0

Queue: [(1, hd=0)]
Top view map: {}

Why: We begin from root to explore all nodes level by level with their horizontal distances

Step 2: Dequeue (1, hd=0), add 1 to top view map at hd=0

Queue: []
Top view map: {0: 1}

Why: First node at hd=0 is 1, so it is visible from top

Step 3: Enqueue left child (2, hd=-1) and right child (3, hd=1)

Queue: [(2, hd=-1), (3, hd=1)]
Top view map: {0: 1}

Why: Children are added with their horizontal distances for further processing

Step 4: Dequeue (2, hd=-1), add 2 to top view map at hd=-1

Queue: [(3, hd=1)]
Top view map: {-1: 2, 0: 1}

Why: First node at hd=-1 is 2, so it is visible from top

Step 5: Enqueue right child (4, hd=0)

Queue: [(3, hd=1), (4, hd=0)]
Top view map: {-1: 2, 0: 1}

Why: 4 is at hd=0 but 1 is already recorded, so 4 won't overwrite

Step 6: Dequeue (3, hd=1), add 3 to top view map at hd=1

Queue: [(4, hd=0)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: First node at hd=1 is 3, so it is visible from top

Step 7: Enqueue right child (5, hd=2)

Queue: [(4, hd=0), (5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: 5 is at hd=2, new horizontal distance

Step 8: Dequeue (4, hd=0), hd=0 already has 1, so skip adding 4

Queue: [(5, hd=2)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: Only first node at each hd is visible from top

Step 9: Enqueue right child (6, hd=1)

Queue: [(5, hd=2), (6, hd=1)]
Top view map: {-1: 2, 0: 1, 1: 3}

Why: 6 is at hd=1 but 3 is already recorded

Step 10: Dequeue (5, hd=2), add 5 to top view map at hd=2

Queue: [(6, hd=1)]
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5}

Why: First node at hd=2 is 5

Step 11: Enqueue right child (7, hd=3)

Queue: [(6, hd=1), (7, hd=3)]
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5}

Why: 7 is at hd=3, new horizontal distance

Step 12: Dequeue (6, hd=1), hd=1 already has 3, skip adding 6

Queue: [(7, hd=3)]
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5}

Why: Only first node at each hd is visible

Step 13: Dequeue (7, hd=3), add 7 to top view map at hd=3

Queue: []
Top view map: {-1: 2, 0: 1, 1: 3, 2: 5, 3: 7}

Why: First node at hd=3 is 7

Result:

Top view nodes in order of hd: 2 -> 1 -> 3 -> 5 -> 7

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

class BinaryTree {
    public Node root;

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

        // Map hd to first node data
        var topViewMap = new SortedDictionary<int, int>();

        // Queue stores pairs of node and its horizontal distance
        var queue = new Queue<(Node node, int hd)>();
        queue.Enqueue((root, 0));

        while (queue.Count > 0) {
            var (curr, hd) = queue.Dequeue();

            // If hd not seen before, add node data
            if (!topViewMap.ContainsKey(hd)) {
                topViewMap[hd] = curr.data;
            }

            if (curr.left != null) queue.Enqueue((curr.left, hd - 1));
            if (curr.right != null) queue.Enqueue((curr.right, hd + 1));
        }

        foreach (var val in topViewMap.Values) {
            result.Add(val);
        }
        return result;
    }
}

class Program {
    static void Main() {
        var tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.right = new Node(4);
        tree.root.left.right.right = new Node(6);
        tree.root.right.right = new Node(5);
        tree.root.right.right.right = new Node(7);

        var topViewNodes = tree.TopView();
        Console.WriteLine(string.Join(" -> ", topViewNodes) + "");
    }
}

queue.Enqueue((root, 0));

Start BFS from root with horizontal distance 0

var (curr, hd) = queue.Dequeue();

Dequeue next node and its horizontal distance

if (!topViewMap.ContainsKey(hd)) { topViewMap[hd] = curr.data; }

Add node data if this horizontal distance is seen first time

if (curr.left != null) queue.Enqueue((curr.left, hd - 1));

Enqueue left child with hd - 1

if (curr.right != null) queue.Enqueue((curr.right, hd + 1));

Enqueue right child with hd + 1

foreach (var val in topViewMap.Values) { result.Add(val); }

Collect top view nodes in order of horizontal distance

Output

2 -> 1 -> 3 -> 5 -> 7

Complexity Analysis

Time: O(n) because we visit each node once during BFS

Space: O(n) for the queue and map storing nodes and horizontal distances

vs Alternative: Naive approach might try to track all nodes at each horizontal distance and then pick top, which is less efficient

Edge Cases

Empty tree

Returns empty list, no nodes to show

DSA C#

if (root == null) return result;

Tree with single node

Returns list with only root node

DSA C#

if (!topViewMap.ContainsKey(hd)) { topViewMap[hd] = curr.data; }

All nodes on one side (left or right)

Top view shows all nodes in a line

DSA C#

if (curr.left != null) queue.Enqueue((curr.left, hd - 1)); if (curr.right != null) queue.Enqueue((curr.right, hd + 1));

When to Use This Pattern

When asked to print nodes visible from top or side view of a tree, use horizontal distance tracking with BFS to find first nodes at each horizontal distance.

Common Mistakes

Mistake: Overwriting nodes in map for the same horizontal distance
Fix: Only add node data if horizontal distance is not already in the map

Mistake: Using DFS instead of BFS, which may not capture top nodes correctly
Fix: Use BFS to process nodes level by level ensuring first node at each horizontal distance is recorded

Summary

Prints nodes visible when looking at the binary tree from above.

Use when you need to find the top view of a tree, showing nodes not hidden behind others.

Track horizontal distances during BFS and record the first node seen at each distance.

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