Bottom View of Binary Tree in DSA Java - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree is the set of nodes visible when the tree is seen from the bottom. It shows the lowest node at each horizontal distance from the root. This helps us understand the structure of the tree from a different perspective than the usual top or side views.

Why it matters

Without the bottom view, we miss how nodes overlap vertically in a tree. It helps in visualizing and solving problems related to vertical order traversal and understanding the tree's shape in applications like network routing or graphical displays. Without it, some important spatial relationships in the tree remain hidden.

Where it fits

Before learning bottom view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After this, you can explore related views like top view, vertical order traversal, and advanced tree algorithms.

Mental Model

Core Idea

The bottom view shows the lowest node visible at each horizontal position when looking up from below the tree.

Think of it like...

Imagine standing under a group of tall trees and looking up; the bottom view is like seeing the lowest branches or leaves that block your view of anything above them at each position.

          (root)
           1
         /   \
        2     3
       / \     \
      4   5     6

Horizontal distances:
Node 4: -2 | Node 2: -1 | Node 1: 0 | Node 3: 1 | Node 6: 2
Bottom view nodes: 4 -> 2 -> 5 -> 3 -> 6

Build-Up - 6 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes below are connected as branches. For example, node 1 is root, nodes 2 and 3 are children of 1.

Result

You can visualize and traverse a simple binary tree.

Understanding the basic structure of binary trees is essential before exploring any special views or traversals.

2

Foundation

Horizontal Distance Concept in Trees

Concept: Introduce horizontal distance (HD) to locate nodes sideways.

Assign HD=0 to root. Left child decreases HD by 1, right child increases HD by 1. This helps group nodes vertically. For example, root 1 has HD=0, left child 2 has HD=-1, right child 3 has HD=1.

Result

You can assign horizontal distances to all nodes in a tree.

Horizontal distance lets us map nodes to vertical lines, which is key to bottom view.

3

Intermediate

Traversing Tree with Horizontal Distances

Concept: Combine tree traversal with tracking HD and node depth.

Use level order traversal (breadth-first) to visit nodes. Track each node's HD and depth (distance from root). Store nodes in a map keyed by HD, updating with the node having the greatest depth at that HD.

Result

You can identify which node is lowest at each horizontal distance.

Tracking depth ensures we pick the bottom-most node for each vertical line.

4

Intermediate

Building Bottom View Using Map

🤔Before reading on: do you think the bottom view includes the first or last node encountered at each horizontal distance? Commit to your answer.

Concept: Use a map to store the bottom-most node at each HD during traversal.

Initialize an empty map from HD to node value. For each visited node, if its depth is greater or equal to the stored node's depth at that HD, update the map. After traversal, the map contains bottom view nodes.

Result

You get a map of HD to bottom view nodes, representing the bottom view.

Knowing to update the map only when a node is lower prevents incorrect nodes from appearing in the bottom view.

5

Advanced

Implementing Bottom View in Java

🤔Before reading on: do you think a recursive or iterative approach is better for bottom view? Commit to your answer.

Concept: Use a queue for level order traversal and a map to track bottom view nodes.

Create a class to hold node, HD, and depth. Use a queue to traverse level by level. For each node, update the map if current depth is greater or equal. After traversal, print nodes from map sorted by HD.

Result

Java code outputs bottom view nodes in order of HD.

Using level order traversal ensures nodes are processed top-down, making it easier to track bottom nodes.

6

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: do you think nodes with the same HD and depth can appear? How should they be handled? Commit to your answer.

Concept: Consider cases with multiple nodes at same HD and depth, and optimize space/time.

If nodes share HD and depth, the last encountered node in level order is chosen. Use TreeMap for ordered HD keys. Optimize by storing only necessary info and avoiding redundant updates.

Result

Bottom view correctly handles ties and is efficient.

Understanding tie-breaking and data structure choice improves correctness and performance in real systems.

Under the Hood

The algorithm uses level order traversal to visit nodes from top to bottom and left to right. Each node's horizontal distance and depth are tracked. A map stores the node with the greatest depth at each horizontal distance. This ensures the bottom-most node is recorded. Internally, the queue manages traversal order, and the map provides quick updates and lookups by horizontal distance.

Why designed this way?

Level order traversal was chosen because it naturally processes nodes by depth, making it easy to compare and update bottom nodes. Using horizontal distance groups nodes vertically, which is essential for bottom view. Alternatives like inorder or preorder don't provide depth order, making them less suitable. The design balances clarity and efficiency.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Initialize    │
│ queue, map    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ While queue   │
│ not empty:    │
│ - Dequeue node│
│ - Update map  │
│   if deeper   │
│ - Enqueue     │
│   children    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ After loop,   │
│ print map in  │
│ order of HD   │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the bottom view always include the leftmost and rightmost nodes? Commit yes or no.

Common Belief: The bottom view always includes the extreme left and right nodes of the tree.

Reality: The bottom view includes the lowest nodes at each horizontal distance, which may or may not be the extreme nodes if they are blocked by lower nodes.

Why it matters: Assuming extremes are always included can lead to incorrect bottom view results, missing nodes that actually appear in the view.

Quick: Is preorder traversal suitable for bottom view? Commit yes or no.

Common Belief: Any tree traversal method works equally well for bottom view calculation.

Reality: Level order traversal is necessary to process nodes by depth correctly; preorder or inorder do not guarantee this order.

Why it matters: Using wrong traversal can cause incorrect bottom view because nodes are not processed in depth order.

Quick: If two nodes share the same horizontal distance and depth, does the first encountered node always appear in bottom view? Commit yes or no.

Common Belief: The first node encountered at a horizontal distance and depth is always in the bottom view.

Reality: The last node encountered at that position in level order traversal is chosen, as it is considered lower or more visible.

Why it matters: Misunderstanding this can cause wrong nodes to appear in the bottom view, especially in trees with overlapping nodes.

Expert Zone

1

The choice of data structure for the map (HashMap vs TreeMap) affects output order and performance.

2

Tie-breaking when nodes share horizontal distance and depth can affect visual correctness in certain tree shapes.

3

Level order traversal combined with horizontal distance tracking elegantly solves bottom view without complex recursion.

When NOT to use

Bottom view is not suitable when you need full vertical order traversal or top view. For those, use vertical order traversal algorithms or top view algorithms respectively.

Production Patterns

Bottom view is used in graphical rendering of trees, network topology visualization, and in problems requiring vertical slicing of hierarchical data. It is often combined with other views for comprehensive tree analysis.

Connections

Vertical Order Traversal

Bottom view is a subset of vertical order traversal focusing on the lowest nodes per vertical line.

Understanding bottom view helps grasp vertical order traversal, which lists all nodes per vertical line, not just the bottom ones.

Level Order Traversal

Bottom view relies on level order traversal to process nodes by depth.

Mastering level order traversal is key to implementing bottom view correctly and efficiently.

Shadow Casting in Computer Graphics

Bottom view conceptually resembles how shadows are cast from objects blocking light from below.

Recognizing this connection helps understand visibility and occlusion principles in both trees and graphics.

Common Pitfalls

#1 Not updating the map when a node at the same horizontal distance but greater depth is found.

Wrong approach:

if (!map.containsKey(hd)) {
map.put(hd, node);
}

Correct approach:

if (!map.containsKey(hd) || currentDepth >= map.get(hd).depth) {
map.put(hd, node);
}

Root cause:

Assuming the first node at a horizontal distance is always the bottom node, ignoring deeper nodes.

#2 Using preorder traversal which does not guarantee processing nodes by depth.

Wrong approach:

void preorder(Node node, int hd, int depth) {
if (node == null) return;
updateMap(hd, depth, node);
preorder(node.left, hd - 1, depth + 1);
preorder(node.right, hd + 1, depth + 1);
}

Correct approach:

Use level order traversal with a queue to process nodes by increasing depth.

Root cause:

Misunderstanding traversal order needed to track bottom nodes correctly.

#3 Not sorting the map keys before printing bottom view nodes.

Wrong approach:

for (Integer hd : map.keySet()) {
print(map.get(hd).value);
}

Correct approach:

for (Integer hd : new TreeMap<>(map).keySet()) {
print(map.get(hd).value);
}

Root cause:

Ignoring that map iteration order is not guaranteed, leading to unordered output.

Key Takeaways

Bottom view shows the lowest visible nodes at each horizontal distance in a binary tree.

Horizontal distance and depth tracking are essential to identify bottom view nodes.

Level order traversal is the best method to process nodes by depth for bottom view.

Using a map keyed by horizontal distance helps store and update bottom nodes efficiently.

Handling edge cases like ties and output ordering ensures correct and clear bottom view results.

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