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

Bottom View of Binary Tree

📖 Scenario: Imagine you are working on a software that visualizes trees from different angles. One important view is the bottom view of a binary tree, which shows the nodes visible when the tree is seen from the bottom.

🎯 Goal: You will build a Java program that finds the bottom view of a binary tree. The bottom view contains the nodes that are visible when the tree is viewed from below, showing the lowest node at each horizontal distance.

📋 What You'll Learn

Create a binary tree with specific nodes and structure

Use a variable to track horizontal distances

Implement the logic to find the bottom view using a queue and a map

Print the bottom view nodes from left to right

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree is useful in graphical visualizations, network routing, and understanding hierarchical data from different perspectives.

💼 Career

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

1

Create the Binary Tree

Create a class called Node with integer data, and Node references left and right. Then create the binary tree root node called root with value 20. Add left child with value 8 and right child with value 22. Add left child of 8 as 5 and right child of 8 as 3. Add left child of 3 as 10 and right child of 3 as 14. Add right child of 22 as 25.

DSA Java

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

Hint

Define the Node class first, then create the tree nodes and link them as children.

2

Add a Map to Track Horizontal Distances

Inside the main method, create a java.util.TreeMap<Integer, Integer> called bottomViewMap to store horizontal distance as key and node data as value.

DSA Java

class Node {
    int data;
    Node left, right;

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

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.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        // Create TreeMap to store horizontal distance and node data
        // Your code here
    }
}

Hint

Use TreeMap<Integer, Integer> to keep keys sorted by horizontal distance.

3

Implement Bottom View Logic

Add code inside main to use a java.util.Queue of Pair objects, where Pair holds a Node and its horizontal distance. Traverse the tree level by level, updating bottomViewMap with the node data for each horizontal distance. Define a static inner class Pair with Node node and int hd. Enqueue the root with horizontal distance 0. For each dequeued Pair, update bottomViewMap and enqueue left child with hd - 1 and right child with hd + 1.

DSA Java

import java.util.TreeMap;
import java.util.Queue;
import java.util.LinkedList;

class Node {
    int data;
    Node left, right;

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

public class BottomView {
    static class Pair {
        Node node;
        int hd;
        Pair(Node node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    }

    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.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        TreeMap bottomViewMap = new TreeMap();

        // Implement bottom view traversal using queue and map
        // Your code here
    }
}

Hint

Use a queue to do level order traversal. Update the map with the latest node at each horizontal distance.

4

Print the Bottom View

After the traversal loop, use a for loop to iterate over bottomViewMap.entrySet() and print the values separated by spaces on one line.

DSA Java

import java.util.TreeMap;
import java.util.Queue;
import java.util.LinkedList;

class Node {
    int data;
    Node left, right;

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

public class BottomView {
    static class Pair {
        Node node;
        int hd;
        Pair(Node node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    }

    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.left.right.left = new Node(10);
        root.left.right.right = new Node(14);
        root.right.right = new Node(25);

        TreeMap bottomViewMap = new TreeMap();

        Queue queue = new LinkedList();
        queue.add(new Pair(root, 0));

        while (!queue.isEmpty()) {
            Pair temp = queue.poll();
            bottomViewMap.put(temp.hd, temp.node.data);

            if (temp.node.left != null) {
                queue.add(new Pair(temp.node.left, temp.hd - 1));
            }
            if (temp.node.right != null) {
                queue.add(new Pair(temp.node.right, temp.hd + 1));
            }
        }

        // Print the bottom view nodes from left to right
        // Your code here
    }
}

Hint

Iterate over the map values and print them separated by spaces on one line.

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