Top View of Binary Tree in DSA Java - Build from Scratch

Top View of Binary Tree

📖 Scenario: You are working on a program that helps visualize a binary tree from the top. Imagine standing above a tree and looking down. Some nodes might hide others behind them. Your task is to find which nodes are visible from this top view.

🎯 Goal: Build a Java program that creates a binary tree, sets a horizontal distance limit, finds the top view nodes of the tree, and prints them in order from left to right.

📋 What You'll Learn

Create a binary tree with given nodes and structure

Use a variable to track horizontal distance limits

Implement logic to find the top view nodes of the binary tree

Print the top view nodes in order from leftmost to rightmost

💡 Why This Matters

🌍 Real World

Top view of a binary tree helps in visualizing hierarchical data from a specific perspective, useful in graphics, network routing, and organizational charts.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a class called Node with integer data, and Node references left and right. Then create a binary tree with root node root having value 1. Set root.left to a node with value 2 and root.right to a node with value 3. Set root.left.right to a node with value 4 and root.left.right.right to a node with value 5. Finally, set root.left.right.right.right to a node with value 6.

DSA Java

// Define Node class and create the binary tree structure
// Your code here

Hint

Start by defining the Node class with data, left, and right. Then create the nodes and link them as described.

2

Set Horizontal Distance Limits

Inside the main method, create two integer variables called minHd and maxHd and set both to 0. These will track the minimum and maximum horizontal distances seen in the tree.

DSA Java

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.left.right.right = new Node(5);
        root.left.right.right.right = new Node(6);

        // Create minHd and maxHd variables
        // Your code here
    }
}

Hint

Declare two integer variables minHd and maxHd and initialize both to zero inside the main method.

3

Implement Top View Logic

Add a static method called printTopView that takes a Node root parameter. Use a TreeMap<Integer, Integer> to store the first node data at each horizontal distance. Use a queue to do a level order traversal. Track horizontal distance for each node. For each node, if its horizontal distance is not in the map, add it. Update minHd and maxHd accordingly. Call printTopView(root) inside main.

DSA Java

    static class QueueObj {
        Node node;
        int hd;
        QueueObj(Node node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    public static void printTopView(Node root) {
        if (root == null) return;
        TreeMap map = new TreeMap();
        Queue queue = new LinkedList();
        queue.add(new QueueObj(root, 0));
        while (!queue.isEmpty()) {
            QueueObj temp = queue.poll();
            int hd = temp.hd;
            Node node = temp.node;
            if (!map.containsKey(hd)) {
                map.put(hd, node.data);
            }
            if (node.left != null) {
                queue.add(new QueueObj(node.left, hd - 1));
            }
            if (node.right != null) {
                queue.add(new QueueObj(node.right, hd + 1));
            }
        }
        for (int key : map.keySet()) {
            System.out.print(map.get(key) + " ");
        }
        printTopView(root);

Hint

Use a queue to do level order traversal. Track horizontal distance for each node. Use a map to store the first node at each horizontal distance. Print the map values in order.

4

Print the Top View Output

Ensure the printTopView(root) method prints the top view nodes separated by spaces in one line. Run the program to display the top view of the binary tree.

DSA Java

Hint

Run the program and check the printed output. It should show the top view nodes separated by spaces in one line.

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