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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the output of the bottom view traversal for the given binary tree?

DSA Java

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

// Tree structure:
//        20
//       /  \
//     8     22
//    / \      \
//   5   3      25
//      / \      
//     10  14

// Bottom view expected output: 5 10 3 14 25

public class BottomView {
    public static void main(String[] args) {
        Node root = new Node(20);
        root.left = new Node(8);
        root.right = new Node(22);
        root.left.left = new Node(5);
        root.left.right = new Node(3);
        root.right.right = new Node(25);
        root.left.right.left = new Node(10);
        root.left.right.right = new Node(14);

        // Assume bottomView(root) returns a list of integers representing bottom view
        System.out.println(bottomView(root));
    }

    // Dummy method for illustration
    static java.util.List<Integer> bottomView(Node root) {
        return java.util.Arrays.asList(5, 10, 3, 14, 25);
    }
}

A [5, 8, 3, 14, 25]

B [5, 10, 3, 22, 25]

C [5, 10, 3, 14, 25]

D [20, 8, 3, 14, 25]

💡 Hint

Bottom view shows the last node visible at each horizontal distance from the root.

The bottom view includes nodes visible when the tree is viewed from the bottom. Nodes 5, 10, 3, 14, and 25 are the bottom-most nodes at their horizontal distances.

❓ Predict Output

intermediate

Bottom View Output for a Left-Skewed Tree

What will be the bottom view output for this left-skewed binary tree?

DSA Java

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

// Tree structure:
//    1
//   /
//  2
// /
//3

// Bottom view expected output: 3

public class BottomView {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(3);

        System.out.println(bottomView(root));
    }

    static java.util.List<Integer> bottomView(Node root) {
        return java.util.Arrays.asList(3);
    }
}

A [2, 3]

B [1, 2, 3]

C [1]

D [3]

💡 Hint

In a left-skewed tree, bottom view shows the lowest node at the leftmost horizontal distance.

All nodes share the same horizontal distance, but the bottom view shows the lowest node, which is 3.

🔧 Debug

advanced

Identify the Error in Bottom View Implementation

What error will this code produce when trying to compute the bottom view of a binary tree?

DSA Java

import java.util.*;
class Node {
    int data;
    Node left, right;
    Node(int data) { this.data = data; }
}

public class BottomView {
    public static void bottomView(Node root) {
        Map<Integer, Integer> map = 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();
            map.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 key : map.keySet()) {
            System.out.print(map.get(key) + " ");
        }
    }
}

A Output is unordered due to HashMap iteration order

B NullPointerException when root is null

C Compilation error due to missing return type

D Infinite loop due to queue not updating

💡 Hint

HashMap does not guarantee order of keys when iterated.

The code runs without error but prints bottom view nodes in arbitrary order because HashMap keys are unordered. Using TreeMap or sorting keys fixes this.

❓ Predict Output

advanced

Bottom View Output for Tree with Overlapping Horizontal Distances

What is the bottom view output for this binary tree with overlapping horizontal distances?

DSA Java

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

// Tree structure:
//        1
//       / \
//      2   3
//       \   \
//        4   5
//         \   \
//          6   7

// Bottom view expected output: 2 4 6 7

public class BottomView {
    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.right.right = new Node(5);
        root.left.right.right = new Node(6);
        root.right.right.right = new Node(7);

        System.out.println(bottomView(root));
    }

    static java.util.List<Integer> bottomView(Node root) {
        return java.util.Arrays.asList(2, 4, 6, 7);
    }
}

A [4, 6, 7]

B [2, 4, 6, 7]

C [1, 2, 3, 5, 7]

D [2, 3, 5, 7]

💡 Hint

Bottom view shows the last node visible at each horizontal distance from the root.

Nodes 2, 4, 6, and 7 are the bottom-most nodes at their horizontal distances, so they appear in the bottom view.

🧠 Conceptual

expert

Horizontal Distance Concept in Bottom View

Which statement best describes the role of horizontal distance (HD) in computing the bottom view of a binary tree?

A HD helps identify nodes at the same horizontal position; bottom view keeps the last node at each HD.

B HD is used to track vertical levels of nodes to determine top view nodes.

C HD is irrelevant; bottom view depends only on node depth.

D HD is used to sort nodes by their values for bottom view output.

💡 Hint

Think about how nodes align horizontally when viewed from the bottom.

Horizontal distance groups nodes vertically; bottom view shows the last node encountered at each horizontal distance during level order traversal.

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