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

Recall & Review

beginner

What does the 'Top View' of a binary tree represent?

The top view of a binary tree is the set of nodes visible when the tree is viewed from above. It includes the nodes that are the first visible at each horizontal distance from the root.

beginner

How do we determine the horizontal distance (HD) of nodes in a binary tree?

The root node is assigned a horizontal distance (HD) of 0. For any node, its left child has HD = parent's HD - 1, and its right child has HD = parent's HD + 1.

intermediate

Which data structure is commonly used to track nodes and their horizontal distances when finding the top view?

A queue is used for level order traversal, and a map (like TreeMap or HashMap) is used to store the first node encountered at each horizontal distance.

intermediate

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

Because the first node encountered at a horizontal distance during level order traversal is the topmost node visible from above at that horizontal distance.

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, because each node is visited once during the traversal.

What horizontal distance is assigned to the root node in top view calculation?

A -1

B 1

C 0

D Depends on tree height

The root node is always assigned a horizontal distance of 0.

Which traversal method is best suited to find the top view of a binary tree?

A Level order traversal

B Preorder traversal

C Postorder traversal

D Inorder traversal

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

In the top view, if two nodes share the same horizontal distance, which one is included?

A The leftmost node

B The one at the lower level

C The rightmost node

D The one at the higher level

The top view includes the node at the higher level (closer to root) for each horizontal distance.

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

A Stack

B Map

C Queue

D Linked List

A map stores the first node encountered at each horizontal distance.

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

A 2 -> 1 -> 3

B 1 -> 2 -> 3

C 3 -> 1 -> 2

D 1 only

The top view includes left child (2), root (1), and right child (3) in order from left to right.

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

Think about how you see the tree from above and which nodes block others.

Why is level order traversal preferred over inorder or preorder for top view?

Consider the order in which nodes appear when looking from above.

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