Top View of Binary Tree in DSA Java - 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 HD visited?

↓

Skip adding to top view

↓

Continue until queue empty

↓

Print nodes in top view order by HD

Traverse the tree level by level, track horizontal distances (HD). For each HD, keep the first node seen. This forms the top view.

Execution Sample

DSA Java

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

void topView(Node root) {
  // code to print top view
}

Prints the top view of a binary tree by tracking horizontal distances during level order traversal.

Execution Table

Step	Operation	Node Processed (data, HD)	Queue State (data, HD)	Top View Map (HD: data)	Visual State
1	Start with root	(1, 0)	[(1,0)]	{}	Tree: 1 / \ 2 3
2	Dequeue node	(1, 0)	[]	{0:1}	Top view: 1 Queue empty
3	Enqueue left child	(2, -1)	[(2,-1)]	{0:1}	Add node 2 at HD -1
4	Enqueue right child	(3, 1)	[(2,-1), (3,1)]	{0:1}	Add node 3 at HD 1
5	Dequeue node	(2, -1)	[(3,1)]	{0:1, -1:2}	Top view: 2,1
6	Enqueue left child	(4, -2)	[(3,1), (4,-2)]	{0:1, -1:2}	Add node 4 at HD -2
7	Enqueue right child	(5, 0)	[(3,1), (4,-2), (5,0)]	{0:1, -1:2}	Node 5 at HD 0 ignored (already present)
8	Dequeue node	(3, 1)	[(4,-2), (5,0)]	{0:1, -1:2, 1:3}	Top view: 2,1,3
9	Enqueue right child	(6, 2)	[(4,-2), (5,0), (6,2)]	{0:1, -1:2, 1:3}	Add node 6 at HD 2
10	Dequeue node	(4, -2)	[(5,0), (6,2)]	{0:1, -1:2, 1:3, -2:4}	Top view: 4,2,1,3
11	Dequeue node	(5, 0)	[(6,2)]	{0:1, -1:2, 1:3, -2:4}	Node 5 at HD 0 ignored
12	Dequeue node	(6, 2)	[]	{0:1, -1:2, 1:3, -2:4, 2:6}	Top view: 4,2,1,3,6
13	Queue empty	-	[]	{-2:4, -1:2, 0:1, 1:3, 2:6}	Traversal complete

💡 Queue is empty, all nodes processed, top view map finalized

Variable Tracker

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

Key Moments - 3 Insights

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

Because the top view shows the first node seen at each horizontal distance during level order traversal. Later nodes at the same horizontal distance are hidden behind earlier ones. See steps 7 and 11 in execution_table where nodes at HD 0 are ignored.

Why do we use horizontal distance (HD) and how is it assigned?

HD helps identify vertical alignment of nodes. Root is at HD 0, left child is HD -1, right child is HD +1. This lets us group nodes vertically. See concept_flow and execution_table steps where HD changes with child nodes.

Why do we use a queue for traversal instead of recursion?

Queue enables level order traversal, which processes nodes top-down and left-right. This order ensures the first node at each HD is recorded. Recursion (like DFS) might visit nodes in a different order, missing the top view. See concept_flow and execution_table for queue usage.

Visual Quiz - 3 Questions

Look at the execution_table, what is the top view map after step 8?

A {0:1, -1:2, 1:3}

B {0:1, -1:2}

C {0:1, 1:3}

D {-1:2, 1:3}

💡 Hint

Check the 'Top View Map' column at step 8 in execution_table

At which step does the queue become empty, ending the traversal?

A Step 12

B Step 13

C Step 10

D Step 5

💡 Hint

Look for the row where 'Queue State' is empty and operation is 'Queue empty'

If node 5 was not ignored at HD 0, how would the top view map change after step 7?

A {0:5, -1:2}

B {0:1, -1:2}

C {-1:2}

D {0:5}

💡 Hint

Refer to step 7 in execution_table where node 5 at HD 0 is ignored because HD 0 already has node 1

Concept Snapshot

Top View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (HD) for each node
- For each HD, keep first node encountered
- Ignore later nodes at same HD
- Print nodes sorted by HD for top view

Full Transcript

This visualization shows how to find the top view of a binary tree. We start at the root with horizontal distance zero. We use a queue to do level order traversal. For each node, we check if its horizontal distance is already recorded in the top view map. If not, we add it. We enqueue left and right children with HD-1 and HD+1 respectively. We continue until the queue is empty. The top view map then contains the first nodes seen at each horizontal distance, representing the top view of the tree.

Practice

1. What does the top view of a binary tree represent?

easy

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

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

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

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 vertically from above the tree.

2. Step 2: Compare with other views

   Left view shows nodes from the left side, right view from the right side, and leaf nodes are only the bottom nodes. So, only top view matches nodes visible from above.

3. Final Answer:

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

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 view
• Thinking top view includes all leaf nodes
• Assuming top view is the same as level order traversal

2. Which data structure is commonly used to store nodes while computing the top view of a binary tree in Java?

easy

A. Stack

B. ArrayList

C. HashMap

D. Queue

Solution

1. Step 1: Identify traversal method for top view

   Top view is usually found using level order traversal, which requires a queue to process nodes level by level.

2. Step 2: Understand role of other data structures

   HashMap is used to store horizontal distances but queue is essential to traverse nodes in order. Stack and ArrayList are not suitable for level order traversal.

3. Final Answer:

   Queue -> Option D

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal in top view [OK]

Common Mistakes:

• Using stack instead of queue for traversal
• Confusing storage with traversal data structure
• Ignoring the need for horizontal distance mapping

3. What is the output of the top view traversal for the following binary tree?

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

medium

A. [2, 1, 3, 4, 7]

B. [2, 1, 3, 5, 7]

C. [2, 1, 4, 6, 7]

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

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 is right child of 2, HD=0. Node 5 is right child of 3, HD=2. Node 6 is right child of 4, HD=1. Node 7 is right child of 5, HD=3.

2. Step 2: Select first node at each HD from top to bottom

   At HD=-1: 2, HD=0: 1, HD=1: 3, HD=2: 5, HD=3: 7. Nodes 4 and 6 are hidden behind 1 and 3 respectively.

3. Final Answer:

   [2, 1, 3, 5, 7] -> Option B

4. Quick Check:

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

Hint: Pick first node at each horizontal distance [OK]

Common Mistakes:

• Including nodes hidden behind others at same horizontal distance
• Mixing order of nodes in output
• Ignoring horizontal distance calculation

4. Identify the error in this Java snippet for top view of a binary tree:

Map map = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  Node temp = queue.poll();
  int hd = temp.hd;
  if (!map.containsKey(hd)) {
    map.put(hd, temp.data);
  }
  if (temp.left != null) {
    temp.left.hd = hd - 1;
    queue.add(temp.left);
  }
  if (temp.right != null) {
    temp.right.hd = hd + 1;
    queue.add(temp.right);
  }
}

medium

A. Horizontal distance (hd) is not initialized for root node

B. Using HashMap instead of TreeMap causes wrong order

C. Queue should be a Stack for correct traversal

D. map.put overwrites existing keys causing wrong output

Solution

1. Step 1: Check initialization of horizontal distance

   The root node's horizontal distance (hd) must be set before adding to queue. Here, root.hd is not initialized, so hd is zero by default or undefined.

2. Step 2: Understand impact of missing hd initialization

   Without root.hd set, all subsequent hd calculations are incorrect, leading to wrong top view nodes.

3. Final Answer:

   Horizontal distance (hd) is not initialized for root node -> Option A

4. Quick Check:

   Root hd must be set before traversal [OK]

Hint: Always initialize root horizontal distance before traversal [OK]

Common Mistakes:

• Forgetting to set root.hd = 0
• Using Stack instead of Queue for level order
• Assuming HashMap order is sorted

5. Given a binary tree where multiple nodes share the same horizontal distance, how can you modify the top view algorithm to print nodes in order from leftmost to rightmost horizontal distance?

hard

A. Use a TreeMap to store horizontal distances and their nodes

B. Use a HashSet to track visited nodes only

C. Use a Stack to reverse the order of nodes after traversal

D. Use a LinkedList to store nodes in insertion order

Solution

1. Step 1: Understand the need for ordered horizontal distances

   Top view nodes must be printed from leftmost (lowest HD) to rightmost (highest HD). HashMap does not maintain order.

2. Step 2: Use TreeMap for sorted keys

   TreeMap stores keys in sorted order automatically, so storing HD as keys and node data as values allows ordered traversal for printing.

3. Final Answer:

   Use a TreeMap to store horizontal distances and their nodes -> Option A

4. Quick Check:

   TreeMap keeps keys sorted for ordered output [OK]

Hint: Use TreeMap to keep horizontal distances sorted [OK]

Common Mistakes:

• Using HashMap and expecting sorted output
• Trying to reverse order with stack instead of sorting keys
• Ignoring horizontal distance ordering