Top View of Binary Tree in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the Node class with integer data.

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int [1]) {
        this.data = data;
        left = right = null;
    }
}

Drag options to blanks, or click blank then click option'

Adata

Bvalue

Cnode

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different parameter name like 'value' without changing the assignment.

Forgetting to assign the parameter to the field.

The constructor parameter should be named 'data' to assign it correctly to the node's data field.

2fill in blank

medium

Complete the code to add a node to the queue.

DSA Java

Queue<Node> queue = new LinkedList<>();
Node root = new Node(10);
queue.[1](root);

Drag options to blanks, or click blank then click option'

Aadd

Boffer

Cinsert

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' which is for stacks, not queues.

Using 'insert' which is not a Queue method.

The 'offer' method is preferred for queues to add elements safely.

3fill in blank

hard

Fix the error in the code to get the horizontal distance from the map.

DSA Java

Map<Node, Integer> map = new HashMap<>();
int hd = [1](node, 0);

Drag options to blanks, or click blank then click option'

Amap

Bmap.get

Cnode

Dmap.getOrDefault

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'map.get(node)' which can return null and cause errors.

Using 'node' or 'map.get' incorrectly.

Use 'map.getOrDefault(node, 0)' to avoid null if key is missing.

4fill in blank

hard

Fill both blanks to update the horizontal distance and add child nodes to the queue.

DSA Java

if (node.left != null) {
    map.put(node.left, map.get(node) [1] 1);
    queue.[2](node.left);
}

Drag options to blanks, or click blank then click option'

A-

B+

Coffer

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Adding instead of subtracting for left child distance.

Using 'add' instead of 'offer' for queue.

Left child horizontal distance is parent's minus one; use 'offer' to add to queue.

5fill in blank

hard

Fill in the blanks to print the top view nodes in order.

DSA Java

for (Map.Entry<Integer, Integer> entry : map.[1]()) {
    System.out.print(entry.[2] + " ");
}
System.out.println();

Drag options to blanks, or click blank then click option'

AentrySet

Bkey

CgetValue

Dvalues

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'key' instead of 'getValue()' to print node data.

Using 'values()' in the loop header which is not iterable as entries.

Use 'entrySet()' to iterate, 'getValue()' to get node data, and 'values()' is incorrect here.

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