Top View of Binary Tree in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top View for a Simple Binary Tree

What is the printed top view of the binary tree after running the given code?

DSA Java

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

class BinaryTree {
    Node root;

    void topView() {
        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Node> queue = new LinkedList<>();
        Queue<Integer> hdQueue = new LinkedList<>();

        queue.add(root);
        hdQueue.add(0);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            int hd = hdQueue.poll();

            if (!topViewMap.containsKey(hd)) {
                topViewMap.put(hd, temp.data);
            }

            if (temp.left != null) {
                queue.add(temp.left);
                hdQueue.add(hd - 1);
            }

            if (temp.right != null) {
                queue.add(temp.right);
                hdQueue.add(hd + 1);
            }
        }

        for (int value : topViewMap.values()) {
            System.out.print(value + " ");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree 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(5);
        tree.root.left.right.right.right = new Node(6);

        tree.topView();
    }
}

A 2 1 3 6

B 2 4 1 3 6

C 1 2 3 4 5 6

D 1 2 3 6

💡 Hint

Think about horizontal distances and which nodes appear first at each horizontal distance.

The top view prints nodes visible when the tree is viewed from above. It uses horizontal distance (hd) from root. The first node encountered at each hd is printed.

Here, nodes with hd -1, 0, 1, 2 are 2, 1, 3, 6 respectively.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Top View

In the top view of a binary tree, what does the horizontal distance (hd) represent?

A The depth of the node from the root

B The vertical level of the node in the tree

C The distance of the node from the root node horizontally, with root at 0

D The number of nodes in the subtree rooted at the node

💡 Hint

Think about how nodes are positioned left or right relative to the root.

Horizontal distance is the horizontal offset from the root node. Root is at hd=0, left child is hd-1, right child is hd+1, and so on.

🔧 Debug

advanced

Identify the Error in Top View Implementation

What error will occur when running the following code snippet for top view of a binary tree?

DSA Java

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

class BinaryTree {
    Node root;

    void topView() {
        Map<Integer, Integer> topViewMap = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        Queue<Integer> hdQueue = new LinkedList<>();

        queue.add(root);
        hdQueue.add(0);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            int hd = hdQueue.poll();

            if (!topViewMap.containsKey(hd)) {
                topViewMap.put(hd, temp.data);
            }

            if (temp.left != null) {
                queue.add(temp.left);
                hdQueue.add(hd - 1);
            }

            if (temp.right != null) {
                queue.add(temp.right);
                hdQueue.add(hd + 1);
            }
        }

        for (int value : topViewMap.values()) {
            System.out.print(value + " ");
        }
    }
}

A Output order is not sorted by horizontal distance

B NullPointerException at runtime

C Compilation error due to missing imports

D No error, code runs and prints top view

💡 Hint

Check the type of Map used and how keys are ordered when iterating.

The code uses HashMap which does not maintain keys in sorted order. So the printed top view nodes are not in horizontal distance order.

To fix, use TreeMap instead of HashMap.

❓ Predict Output

advanced

Top View Output for Complex Tree

What is the output of the top view method for the following binary tree?

DSA Java

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

class BinaryTree {
    Node root;

    void topView() {
        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Node> queue = new LinkedList<>();
        Queue<Integer> hdQueue = new LinkedList<>();

        queue.add(root);
        hdQueue.add(0);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            int hd = hdQueue.poll();

            if (!topViewMap.containsKey(hd)) {
                topViewMap.put(hd, temp.data);
            }

            if (temp.left != null) {
                queue.add(temp.left);
                hdQueue.add(hd - 1);
            }

            if (temp.right != null) {
                queue.add(temp.right);
                hdQueue.add(hd + 1);
            }
        }

        for (int value : topViewMap.values()) {
            System.out.print(value + " ");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(20);
        tree.root.right = new Node(30);
        tree.root.left.left = new Node(40);
        tree.root.left.right = new Node(50);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(70);
        tree.root.right.left.right = new Node(80);
        tree.root.right.right.right = new Node(90);

        tree.topView();
    }
}

A 20 10 30 70 90

B 40 20 10 30 60 70 90

C 40 20 10 30 60 80 90

D 40 20 10 30 70 90

💡 Hint

Remember only the first node at each horizontal distance is printed.

Horizontal distances and first nodes are:

• hd -2: 40
• hd -1: 20
• hd 0: 10
• hd 1: 30
• hd 2: 70
• hd 3: 90

Nodes 60 and 80 are hidden behind others at their horizontal distances.

🚀 Application

expert

Number of Nodes in Top View

Given a binary tree, how many nodes will be printed in its top view if the tree is a perfect binary tree of height 2?

A 7

B 5

C 4

D 3

💡 Hint

Count the unique horizontal distances in a perfect binary tree of height 2.

A perfect binary tree of height 2 has 7 nodes arranged in 3 levels.

Horizontal distances range from -2 to 2, so 5 unique horizontal distances.

Top view prints one node per horizontal distance, so 5 nodes.

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