Bottom View of Binary Tree in DSA Java

Mental Model

We want to see the nodes visible if we look at the tree from the bottom. Each vertical line shows only the lowest node.

Analogy: Imagine standing under a tree and looking up. You only see the lowest leaves or branches directly above you, not the ones behind or higher up.

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

Vertical lines: -2  -1   0   1   2
Nodes:          5   8  10  14  25
Bottom view: 5 -> 10 -> 3 -> 14 -> 25 -> null

Dry Run Walkthrough

Input: Binary tree: 20 / \ 8 22 / \ \ 5 3 25 / \ 10 14

Goal: Find the bottom view nodes of the tree, showing the lowest node at each vertical line from left to right.

Step 1: Start at root 20 with horizontal distance (hd) = 0

hd=0: 20
Queue: [(20,0)]

Why: We begin from the root at horizontal distance zero.

Step 2: Process node 20, update map hd=0 -> 20, enqueue left child 8 (hd=-1), right child 22 (hd=1)

Map: {-1: -, 0: 20, 1: -}
Queue: [(8,-1), (22,1)]

Why: Store node 20 for hd=0, add children with updated hd.

Step 3: Process node 8, update map hd=-1 -> 8, enqueue left child 5 (hd=-2), right child 3 (hd=0)

Map: {-2: -, -1: 8, 0: 20, 1: -}
Queue: [(22,1), (5,-2), (3,0)]

Why: Node 8 is lower at hd=-1, add its children.

Step 4: Process node 22, update map hd=1 -> 22, enqueue right child 25 (hd=2)

Map: {-2: -, -1: 8, 0: 20, 1: 22, 2: -}
Queue: [(5,-2), (3,0), (25,2)]

Why: Node 22 is lowest so far at hd=1, add child 25.

Step 5: Process node 5, update map hd=-2 -> 5, no children to enqueue

Map: {-2: 5, -1: 8, 0: 20, 1: 22, 2: -}
Queue: [(3,0), (25,2)]

Why: Node 5 is lowest at hd=-2.

Step 6: Process node 3, update map hd=0 -> 3, enqueue left child 10 (hd=-1), right child 14 (hd=1)

Map: {-2: 5, -1: 8, 0: 3, 1: 22, 2: -}
Queue: [(25,2), (10,-1), (14,1)]

Why: Node 3 is lower than 20 at hd=0, add children.

Step 7: Process node 25, update map hd=2 -> 25, no children

Map: {-2: 5, -1: 8, 0: 3, 1: 22, 2: 25}
Queue: [(10,-1), (14,1)]

Why: Node 25 is lowest at hd=2.

Step 8: Process node 10, update map hd=-1 -> 10, no children

Map: {-2: 5, -1: 10, 0: 3, 1: 22, 2: 25}
Queue: [(14,1)]

Why: Node 10 is lower than 8 at hd=-1.

Step 9: Process node 14, update map hd=1 -> 14, no children

Map: {-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}
Queue: []

Why: Node 14 is lower than 22 at hd=1.

Result:

Bottom view nodes from left to right:
5 -> 10 -> 3 -> 14 -> 25 -> null

Annotated Code

DSA Java

import java.util.*;

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

public class BottomViewBinaryTree {

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

    public static List<Integer> bottomView(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Map<Integer, Integer> map = new TreeMap<>(); // hd -> node.data
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, 0));

        while (!queue.isEmpty()) {
            Pair curr = queue.poll();
            // overwrite map entry for hd with current node's data
            map.put(curr.hd, curr.node.data);

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

        for (int val : map.values()) {
            result.add(val);
        }
        return result;
    }

    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);

        List<Integer> bottomViewNodes = bottomView(root);
        for (int val : bottomViewNodes) {
            System.out.print(val + " -> ");
        }
        System.out.print("null\n");
    }
}

map.put(curr.hd, curr.node.data);

overwrite map entry for horizontal distance with current node's data to keep lowest node

queue.add(new Pair(curr.node.left, curr.hd - 1));

enqueue left child with horizontal distance decreased by 1

queue.add(new Pair(curr.node.right, curr.hd + 1));

enqueue right child with horizontal distance increased by 1

Output

5 -> 10 -> 3 -> 14 -> 25 -> null

Complexity Analysis

Time: O(n) because we visit each node once in level order traversal

Space: O(n) for the queue and map storing nodes and horizontal distances

vs Alternative: Compared to recursive vertical order traversal, this BFS approach is simpler and uses a map to overwrite nodes at each horizontal distance, ensuring bottom nodes are recorded.

Edge Cases

Empty tree (root is null)

Returns empty list, no nodes to show

DSA Java

if (root == null) return result;

Tree with single node

Returns list with only that node

DSA Java

queue.add(new Pair(root, 0));

Multiple nodes at same horizontal distance and level

Bottom-most node overwrites previous nodes in map

DSA Java

map.put(curr.hd, curr.node.data);

When to Use This Pattern

When asked to find nodes visible from the bottom of a binary tree, use a level order traversal with horizontal distances and overwrite nodes at each horizontal distance to get the bottom view.

Common Mistakes

Mistake: Not updating the map to overwrite nodes at the same horizontal distance, so top nodes remain instead of bottom nodes.
Fix: Always overwrite the map entry for the horizontal distance with the current node's data during BFS.

Summary

Shows the lowest nodes visible when looking at a binary tree from the bottom.

Use when you need to find nodes visible from the bottom perspective of a tree.

Keep track of horizontal distances and overwrite nodes at each 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