Bottom 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

BnodeData

Cvalue

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Using a parameter name different from the field without assignment.

Forgetting to assign the parameter to the field.

The constructor parameter should be named 'data' to match the assignment 'this.data = data;'.

2fill in blank

medium

Complete the code to initialize the horizontal distance map in the bottom view method.

DSA Java

Map<Integer, Integer> map = new TreeMap<>();
Queue<Pair<Node, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(root, [1]));

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

A0

B1

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Starting horizontal distance at 1 or -1 instead of 0.

Using null which is invalid for an integer.

The root node's horizontal distance is initialized to 0.

3fill in blank

hard

Fix the error in updating the map with the bottom view node data.

DSA Java

while (!queue.isEmpty()) {
    Pair<Node, Integer> temp = queue.poll();
    Node node = temp.getKey();
    int hd = temp.getValue();
    map.put(hd, [1]);
    if (node.left != null) queue.add(new Pair<>(node.left, hd - 1));
    if (node.right != null) queue.add(new Pair<>(node.right, hd + 1));
}

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

Anode

Bnode.data

Ctemp.getKey()

Dhd

Attempts:

3 left

💡 Hint

Common Mistakes

Storing the horizontal distance instead of node data.

Storing the node object instead of its data.

We store the node's data at the horizontal distance in the map for bottom view.

4fill in blank

hard

Fill both blanks to complete the method that returns the bottom view list.

DSA Java

public List<Integer> bottomView(Node root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Map<Integer, Integer> map = new TreeMap<>();
    Queue<Pair<Node, Integer>> queue = new LinkedList<>();
    queue.add(new Pair<>(root, 0));
    while (!queue.isEmpty()) {
        Pair<Node, Integer> temp = queue.poll();
        Node node = temp.getKey();
        int hd = temp.getValue();
        map.put(hd, node.data);
        if (node.left != null) queue.add(new Pair<>(node.left, hd [1] 1));
        if (node.right != null) queue.add(new Pair<>(node.right, hd [2] 1));
    }
    for (int val : map.values()) result.add(val);
    return result;
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition for left child or subtraction for right child.

Using multiplication or division which is incorrect.

Left child horizontal distance is hd - 1; right child is hd + 1.

5fill in blank

hard

Fill all three blanks to complete the Pair class usage and map iteration.

DSA Java

Queue<Pair<Node, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>([1], [2]));

for (Map.Entry<Integer, Integer> entry : map.[3]()) {
    result.add(entry.getValue());
}

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

Aroot

B0

CentrySet

DkeySet

Attempts:

3 left

💡 Hint

Common Mistakes

Using keySet() instead of entrySet() for map iteration.

Using null or wrong values in Pair constructor.

We add root with horizontal distance 0; iterate map entries with entrySet().

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes that are visible when looking at the tree from below, ignoring nodes hidden behind others.

2. Step 2: Compare with other views

   Top, left, and right views show nodes from different directions, but bottom view specifically shows the lowest nodes at each horizontal distance.

3. Final Answer:

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

4. Quick Check:

   Bottom view = visible nodes from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking it shows all leaf nodes
• Mixing bottom view with side views

2. Which data structure is commonly used to store nodes along with their horizontal distance while computing the bottom view of a binary tree in Java?

easy

A. HashMap

B. Queue

C. ArrayList

D. Stack

Solution

1. Step 1: Identify the need to map horizontal distances

   We need to store nodes with their horizontal distance to update the bottom-most node at each distance.

2. Step 2: Choose appropriate data structure

   A HashMap stores key-value pairs efficiently, mapping horizontal distance (key) to node data (value).

3. Final Answer:

   HashMap -> Option A

4. Quick Check:

   Use HashMap for horizontal distance mapping [OK]

Hint: Use HashMap to map horizontal distance to node [OK]

Common Mistakes:

• Using Stack which is LIFO, not suitable here
• Using Queue alone without mapping distances
• Using ArrayList which doesn't map keys

3. What is the output bottom view of the following binary tree?

        20
       /  \
     8     22
    / \      \
   5   3      25
      /  \
     10   14

medium

A. [5, 8, 10, 14, 25]

B. [5, 10, 3, 14, 25]

C. [5, 10, 3, 22, 25]

D. [8, 10, 3, 14, 22]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1). Bottom nodes at each distance are the lowest nodes: -2:5, -1:10, 0:3, 1:14, 2:25.

2. Step 2: Collect bottom view nodes in order from left to right

   Order by horizontal distance: 5, 10, 3, 14, 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option B

4. Quick Check:

   Bottom view nodes = [5, 10, 3, 14, 25] [OK]

Hint: Track horizontal distance and update bottom nodes [OK]

Common Mistakes:

• Not updating bottom node when lower node appears
• Mixing horizontal distances order
• Including nodes not visible from bottom

4. Identify the error in this Java snippet for bottom view calculation:

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

void bottomView(Node root) {
  Map map = new HashMap<>();
  Queue<Node> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    Node temp = queue.poll();
    int hd = 0; // horizontal distance
    map.put(hd, temp.data);
    if (temp.left != null) queue.add(temp.left);
    if (temp.right != null) queue.add(temp.right);
  }
  System.out.println(map.values());
}

medium

A. Queue should be a Stack for bottom view

B. Missing check for null root before processing

C. Map should store Node objects, not integers

D. Horizontal distance 'hd' is reset to 0 inside the loop

Solution

1. Step 1: Analyze horizontal distance usage

   The variable 'hd' is reset to 0 inside the loop, so all nodes get the same horizontal distance, which is incorrect.

2. Step 2: Understand horizontal distance tracking

   Horizontal distance must be tracked per node and updated when adding children (left: hd-1, right: hd+1).

3. Final Answer:

   Horizontal distance 'hd' is reset to 0 inside the loop -> Option D

4. Quick Check:

   hd must update per node, not reset [OK]

Hint: Track horizontal distance outside loop and update per node [OK]

Common Mistakes:

• Resetting horizontal distance inside loop
• Using Stack instead of Queue for BFS
• Not updating horizontal distance for children

5. Given a binary tree where multiple nodes share the same horizontal distance and depth, how should the bottom view algorithm decide which node to show?

hard

A. Show the node that appears last in level order traversal at that horizontal distance

B. Show the node with the smallest value at that horizontal distance

C. Show the node that appears first in level order traversal at that horizontal distance

D. Show all nodes at that horizontal distance

Solution

1. Step 1: Understand bottom view node selection

   Bottom view shows the lowest node at each horizontal distance. When nodes share horizontal distance and depth, the one encountered last in level order (BFS) is the bottom-most.

2. Step 2: Confirm BFS traversal order

   Level order traversal visits nodes top to bottom, left to right. Updating map with each node at horizontal distance ensures last node overwrites previous.

3. Final Answer:

   Show the node that appears last in level order traversal at that horizontal distance -> Option A

4. Quick Check:

   Bottom view = last node at horizontal distance in BFS [OK]

Hint: Update map with last node at horizontal distance during BFS [OK]

Common Mistakes:

• Choosing first node instead of last at horizontal distance
• Selecting node by value instead of position
• Trying to show multiple nodes per horizontal distance