Bottom View of Binary Tree in DSA Java - Execution Trace

Concept Flow - Bottom View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

For each node dequeued:

↓

Record node data at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

After traversal, extract nodes with max depth at each horizontal distance

↓

Print bottom view from leftmost to rightmost horizontal distance

Traverse the tree level by level, track horizontal distances, update bottom nodes, then print from left to right.

Execution Sample

DSA Java

import java.util.*;

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

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

  public static void bottomView(Node root) {
    if (root == null) return;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 0));
    while (!queue.isEmpty()) {
      Pair p = queue.poll();
      map.put(p.hd, p.node.data);
      if (p.node.left != null)
        queue.add(new Pair(p.node.left, p.hd - 1));
      if (p.node.right != null)
        queue.add(new Pair(p.node.right, p.hd + 1));
    }
    for (int val : map.values()) {
      System.out.print(val + " ");
    }
    System.out.println();
  }
}

// Bottom view function uses level order traversal with horizontal distances

This code traverses the binary tree level-wise, tracks horizontal distances, and updates the bottom view nodes.

Execution Table

Step	Operation	Node Visited (data)	Horizontal Distance (hd)	Map Update (hd -> node)	Queue State	Bottom View Visual State
1	Start at root	20	0	{0 -> 20}	[(20,0)]	hd=0:20
2	Dequeue node	20	0	{0 -> 20}	[]	hd=0:20
3	Enqueue left child	8	-1	{0 -> 20}	[(8,-1)]	hd=0:20
4	Enqueue right child	22	1	{0 -> 20}	[(8,-1),(22,1)]	hd=0:20
5	Dequeue node	8	-1	{0 -> 20, -1 -> 8}	[(22,1)]	hd=-1:8, 0:20
6	Enqueue left child	5	-2	{0 -> 20, -1 -> 8}	[(22,1),(5,-2)]	hd=-1:8, 0:20
7	Enqueue right child	3	0	{0 -> 3, -1 -> 8}	[(22,1),(5,-2),(3,0)]	hd=-1:8, 0:3
8	Dequeue node	22	1	{0 -> 3, -1 -> 8, 1 -> 22}	[(5,-2),(3,0)]	hd=-1:8, 0:3, 1:22
9	Enqueue right child	25	2	{0 -> 3, -1 -> 8, 1 -> 22}	[(5,-2),(3,0),(25,2)]	hd=-1:8, 0:3, 1:22
10	Dequeue node	5	-2	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22}	[(3,0),(25,2)]	hd=-2:5, -1:8, 0:3, 1:22
11	Dequeue node	3	0	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22}	[(25,2)]	hd=-2:5, -1:8, 0:3, 1:22
12	Dequeue node	25	2	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22, 2 -> 25}	[]	hd=-2:5, -1:8, 0:3, 1:22, 2:25
13	Traversal complete	N/A	N/A	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22, 2 -> 25}	[]	Bottom view: 5 -> 8 -> 3 -> 22 -> 25

💡 Queue empty, all nodes visited, bottom view map finalized

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 12	Final
Queue	[(20,0)]	[(22,1),(5,-2),(3,0)]	[(3,0),(25,2)]	[]	[]
Map (hd -> node)	{}	{0 -> 20, -1 -> 8}	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22}	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22, 2 -> 25}	{-2 -> 5, -1 -> 8, 0 -> 3, 1 -> 22, 2 -> 25}

Key Moments - 3 Insights

Why does the map update the node at horizontal distance 0 from 20 to 3?

Because node 3 is visited later at the same horizontal distance 0 during level order traversal, it replaces 20 in the map, representing the bottom-most node at hd=0 (see steps 7 and 11).

Why do we use horizontal distance to track nodes?

Horizontal distance helps identify vertical columns in the tree. Nodes with the same hd lie in the same vertical line. The bottom view shows the lowest node at each hd (see map updates in execution_table).

Why do we use a queue for traversal?

Queue enables level order traversal (breadth-first), ensuring nodes are visited top to bottom and left to right, so bottom nodes overwrite top nodes in the map correctly (see queue states in execution_table).

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the map update for horizontal distance 0?

A {0 -> 3, -1 -> 8}

B {-1 -> 8}

C {0 -> 20}

D {0 -> 8}

💡 Hint

Check the 'Map Update' column at step 7 in the execution_table.

At which step does the queue become empty, ending the traversal?

A Step 10

B Step 13

C Step 12

D Step 5

💡 Hint

Look at the 'Queue State' column and the 'Exit Note' in the execution_table.

If the node with data 3 had no right child, how would the map update at horizontal distance 0 change?

A It would remain {0 -> 3}

B It would remain {0 -> 20}

C It would remain {0 -> 8}

D It would remain {0 -> 25}

💡 Hint

Consider that without node 3, the last update at hd=0 would be from node 20 at step 2.

Concept Snapshot

Bottom View of Binary Tree:
- Traverse tree level-wise with a queue
- Track horizontal distance (hd) for each node
- Update map hd -> node with latest node at hd
- After traversal, print nodes from min to max hd
- Shows lowest nodes visible from bottom
- Uses BFS and hd mapping

Full Transcript

The bottom view of a binary tree shows the nodes visible when the tree is viewed from the bottom. We do a level order traversal using a queue, starting from the root with horizontal distance zero. For each node visited, we record or update the node data at its horizontal distance in a map. Left child nodes have hd-1, right child nodes hd+1. Because we traverse level-wise, nodes lower in the tree overwrite nodes above at the same horizontal distance. After visiting all nodes, we print the map entries from the smallest to largest horizontal distance to get the bottom view. This method ensures the bottom-most nodes at each vertical line are shown.

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