Bottom View of Binary Tree in DSA Python - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree shows the nodes visible when the tree is seen from the bottom. It means for each vertical line through the tree, we see the lowest node. This view helps us understand the structure of the tree from a different angle. It is different from top or side views because it focuses on the lowest nodes in each vertical column.

Why it matters

Without the bottom view, we miss how nodes overlap vertically in a tree. This view helps in problems like network routing, visualization, and understanding hierarchical data from a new perspective. It solves the problem of identifying which nodes are visible when looking from below, which is useful in graphical displays and tree analysis.

Where it fits

Before learning bottom view, you should understand binary trees, tree traversal, and the concept of horizontal distance in trees. After this, you can explore related views like top view, left view, and right view of trees, and then move on to more complex tree problems like vertical order traversal.

Mental Model

Core Idea

The bottom view of a binary tree is the set of nodes that appear last at each vertical line when looking from below.

Think of it like...

Imagine standing under a group of tall trees and looking up. The bottom view is like seeing the trunks and branches that are directly above you without anything blocking your view from below.

           (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 - 7 Steps

1

Foundation

Understanding Binary Trees

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 by edges. For example, a root node 1 can have left child 2 and right child 3.

Result

You can visualize and represent a tree with nodes and edges.

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

2

Foundation

Horizontal Distance Concept

Concept: Assign horizontal distances to nodes to identify vertical lines.

Start with the root node at horizontal distance (HD) 0. For each left child, HD decreases by 1. For each right child, HD increases by 1. This helps group nodes vertically. For example, root 1 is HD 0, left child 2 is HD -1, right child 3 is HD 1.

Result

Each node has a horizontal distance value that helps in vertical grouping.

Horizontal distance is the key to mapping nodes to vertical lines for bottom view.

3

Intermediate

Level Order Traversal with HD Tracking

🤔Before reading on: Do you think a depth-first or breadth-first traversal is better to find bottom view? Commit to your answer.

Concept: Use breadth-first (level order) traversal to visit nodes level by level while tracking their horizontal distances.

We use a queue to visit nodes level by level. Each node is stored with its HD. When visiting a node, we update the bottom view map for that HD with the current node's value. This way, the last node visited at each HD is the bottom view node.

Result

A map from HD to node value representing the bottom view is created.

Level order traversal ensures nodes lower in the tree overwrite higher nodes at the same HD, capturing the bottom view.

4

Intermediate

Building Bottom View Map

🤔Before reading on: If two nodes share the same HD but different levels, which one appears in the bottom view? Commit to your answer.

Concept: For each horizontal distance, keep updating the node value as we go deeper in the tree.

As we traverse, if a node at HD x is found, it replaces the previous node at HD x in the map. This means the bottom-most node at each HD remains in the map after traversal.

Result

The map contains the bottom view nodes for all HDs after traversal.

Updating the map during traversal captures the lowest node at each vertical line, which is the essence of bottom view.

5

Intermediate

Extracting and Sorting Bottom View

Concept: Sort the horizontal distances and print corresponding nodes to get the bottom view from left to right.

After traversal, the map keys (HDs) are sorted from smallest to largest. The node values are printed in this order to show the bottom view from left to right.

Result

A list of node values representing the bottom view in correct order.

Sorting HDs ensures the bottom view is presented in a natural left-to-right order.

6

Advanced

Implementing Bottom View in Python

🤔Before reading on: Do you think a dictionary or list is better to store nodes by HD? Commit to your answer.

Concept: Use a dictionary to map HD to node value and a queue for level order traversal.

Code example: class Node: def __init__(self, val): self.val = val self.left = None self.right = None def bottom_view(root): if not root: return [] from collections import deque queue = deque([(root, 0)]) # (node, horizontal distance) hd_node_map = {} while queue: node, hd = queue.popleft() hd_node_map[hd] = node.val # overwrite to keep bottom-most if node.left: queue.append((node.left, hd - 1)) if node.right: queue.append((node.right, hd + 1)) return [hd_node_map[hd] for hd in sorted(hd_node_map)] # Example usage: # Construct tree: # 20 # / \ # 8 22 # / \ \ # 5 3 25 # / \ # 10 14 root = Node(20) root.left = Node(8) root.right = Node(22) root.left.left = Node(5) root.left.right = Node(3) root.right.right = Node(25) root.left.right.left = Node(10) root.left.right.right = Node(14) print(bottom_view(root))

Result

[5, 10, 3, 14, 25]

Using a dictionary keyed by horizontal distance with level order traversal efficiently captures the bottom view.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Can bottom view change if tree nodes have the same horizontal distance and level? Commit to your answer.

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

If two nodes share the same HD and level, the one visited last in level order is chosen. To optimize, we can track levels explicitly and only update if current node is at a deeper or same level. Also, using ordered data structures can improve retrieval speed.

Result

Bottom view correctly reflects the lowest nodes even in complex trees with overlaps.

Understanding tie-breaking and optimization ensures robust bottom view implementations in real-world scenarios.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) to visit nodes level by level. Each node is associated with a horizontal distance (HD). A map stores the latest node value for each HD, effectively overwriting nodes higher up with nodes lower down. This works because level order visits nodes top to bottom, left to right, so the last node at each HD is the bottom-most. Internally, a queue manages traversal order, and a dictionary stores HD-node pairs.

Why designed this way?

This approach was chosen because it efficiently captures the bottom-most nodes without needing multiple passes. Alternatives like depth-first search require more complex tracking of levels and HDs. Level order traversal naturally processes nodes by depth, making it easier to overwrite nodes at the same HD with lower ones. The dictionary provides quick updates and lookups by HD.

┌───────────────┐
│   Start root  │
│ HD = 0       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Enqueue root  │
│ (node, HD=0)  │
└──────┬────────┘
       │
       ▼
┌───────────────────────────────┐
│ While queue not empty          │
│   Dequeue node, HD             │
│   Update map[HD] = node value  │
│   Enqueue left child (HD - 1) │
│   Enqueue right child (HD + 1)│
└──────────────┬────────────────┘
               │
               ▼
┌───────────────────────────────┐
│ After traversal:              │
│ map has bottom nodes per HD   │
│ Sort HD keys and output nodes │
└───────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the bottom view always include the deepest node in the tree? Commit yes or no.

Common Belief: The bottom view always shows the deepest nodes in the tree.

Reality: The bottom view shows the lowest node at each horizontal distance, which may not be the deepest node overall.

Why it matters: Assuming deepest nodes are always in bottom view can lead to incorrect answers, especially when nodes at different horizontal distances have different depths.

Quick: If two nodes share the same horizontal distance but different levels, does the top one appear in bottom view? Commit yes or no.

Common Belief: The top node at a horizontal distance appears in the bottom view.

Reality: The bottom view shows the bottom-most node at that horizontal distance, so the top node is overwritten by lower nodes.

Why it matters: Misunderstanding this causes confusion between top view and bottom view, leading to wrong implementations.

Quick: Can a depth-first traversal alone correctly produce bottom view? Commit yes or no.

Common Belief: Depth-first traversal is sufficient to find bottom view nodes.

Reality: Depth-first traversal alone is not enough because it does not guarantee visiting nodes level by level, which is needed to overwrite nodes correctly.

Why it matters: Using depth-first traversal without level tracking can produce incorrect bottom views.

Expert Zone

1

When nodes share the same horizontal distance and level, the order of traversal determines which node appears in the bottom view.

2

Using a balanced tree can reduce the range of horizontal distances, optimizing space for the map.

3

In very large trees, using a balanced queue and map data structure can improve performance and memory usage.

When NOT to use

Bottom view is not suitable when you need to see all nodes visible from the side or top; use top view or vertical order traversal instead. For trees with weighted edges or non-binary trees, specialized views or algorithms are better.

Production Patterns

Bottom view is used in graphical tree visualizations, network topology mapping, and in problems where vertical layering of hierarchical data matters. It is also used in coding interviews to test understanding of tree traversals and mapping.

Connections

Top View of Binary Tree

Opposite vertical perspective of the same tree structure.

Understanding bottom view helps grasp top view since both use horizontal distances but differ in which node per vertical line is chosen.

Vertical Order Traversal

Builds on horizontal distance grouping but lists all nodes per vertical line.

Knowing bottom view simplifies understanding vertical order traversal as it is a more detailed version showing all nodes instead of just the bottom-most.

Shadow Casting in Computer Graphics

Similar concept of visibility from a viewpoint using projections.

Bottom view in trees is like casting shadows from below; understanding this helps in graphics algorithms that determine visible surfaces.

Common Pitfalls

#1 Not updating the node value for a horizontal distance when a lower node is found.

Wrong approach:

hd_node_map = {}
queue = deque([(root, 0)])
while queue:
node, hd = queue.popleft()
if hd not in hd_node_map:
hd_node_map[hd] = node.val
if node.left:
queue.append((node.left, hd - 1))
if node.right:
queue.append((node.right, hd + 1))

Correct approach:

hd_node_map = {}
queue = deque([(root, 0)])
while queue:
node, hd = queue.popleft()
hd_node_map[hd] = node.val # overwrite to keep bottom-most
if node.left:
queue.append((node.left, hd - 1))
if node.right:
queue.append((node.right, hd + 1))

Root cause:

Misunderstanding that bottom view requires the last node at each horizontal distance, not the first.

#2 Using depth-first traversal without tracking levels to find bottom view.

Wrong approach:

def dfs(node, hd):
if not node:
return
hd_node_map[hd] = node.val
dfs(node.left, hd - 1)
dfs(node.right, hd + 1)

# This overwrites nodes but does not consider depth order.

Correct approach:

Use level order traversal with queue to ensure nodes are processed by depth:
queue = deque([(root, 0)])
while queue:
node, hd = queue.popleft()
hd_node_map[hd] = node.val
if node.left:
queue.append((node.left, hd - 1))
if node.right:
queue.append((node.right, hd + 1))

Root cause:

Not realizing that depth-first traversal does not guarantee bottom-most nodes are processed last.

#3 Not sorting horizontal distances before printing bottom view.

Wrong approach:

print([hd_node_map[hd] for hd in hd_node_map]) # unordered output

Correct approach:

print([hd_node_map[hd] for hd in sorted(hd_node_map)]) # ordered left to right

Root cause:

Ignoring the need to present bottom view nodes in left-to-right order.

Key Takeaways

Bottom view of a binary tree shows the lowest nodes visible at each vertical line when viewed from below.

Horizontal distance is the key concept to group nodes vertically and identify which nodes belong to each vertical line.

Level order traversal with a map keyed by horizontal distance efficiently captures the bottom view by overwriting nodes at the same horizontal distance.

Sorting the horizontal distances before output ensures the bottom view is presented from left to right.

Understanding the difference between bottom view and other views like top view prevents common mistakes in tree visualization problems.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the left side

D. Nodes visible when the tree is viewed from the bottom

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes from above, left and right views show nodes from sides, so bottom view is unique for bottom perspective.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option D

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 bottom view shows all leaf nodes
• Mixing bottom view with side views

2. Which data structure is commonly used to track nodes and their horizontal distances when computing the bottom view of a binary tree?

easy

A. Hash Map (Dictionary)

B. Queue

C. Stack

D. Linked List

Solution

1. Step 1: Identify the need for horizontal distance mapping

   We need to map horizontal distances to nodes to know which node is visible at each position.

2. Step 2: Choose the data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, updating with the bottom-most node.

3. Final Answer:

   Hash Map (Dictionary) -> Option A

4. Quick Check:

   Use dictionary to map horizontal distance to node [OK]

Hint: Use dictionary to map horizontal distance to node [OK]

Common Mistakes:

• Using stack which is LIFO and not suitable here
• Using queue alone without mapping distances
• Using linked list which is inefficient for key-value mapping

3. What is the bottom view output of the following binary tree?

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

medium

A. [5, 10, 3, 14, 25]

B. [5, 8, 10, 14, 25]

C. [5, 10, 3, 22, 25]

D. [8, 10, 3, 14, 22]

Solution

1. Step 1: Assign horizontal distances and find 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: -2:5, -1:10, 0:3, 1:14, 2:25.

2. Step 2: List bottom view nodes in order of horizontal distance

   From left to right: 5, 10, 3, 14, 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option A

4. Quick Check:

   Bottom view nodes by horizontal distance = [5,10,3,14,25] [OK]

Hint: Track horizontal distances and update bottom nodes [OK]

Common Mistakes:

• Not updating bottom node when a lower node appears
• Mixing horizontal distances order
• Including nodes not visible from bottom

4. Consider this code snippet to compute bottom view of a binary tree:

def bottom_view(root):
    if not root:
        return []
    queue = [(root, 0)]
    hd_node = {}
    while queue:
        node, hd = queue.pop()
        hd_node[hd] = node.val
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [hd_node[hd] for hd in sorted(hd_node)]

What is the main error in this code?

medium

A. Not checking if root is None

B. Using pop() removes last element, causing wrong traversal order

C. Not updating hd_node dictionary

D. Incorrect horizontal distance calculation

Solution

1. Step 1: Analyze queue usage and traversal order

   The code uses queue.pop() which removes last element (LIFO), making it behave like a stack, causing depth-first traversal instead of breadth-first.

2. Step 2: Understand impact on bottom view calculation

   Breadth-first traversal is needed to process nodes level by level to correctly update bottom nodes. Using pop() breaks this order.

3. Final Answer:

   Using pop() removes last element, causing wrong traversal order -> Option B

4. Quick Check:

   Use pop(0) or deque.popleft() for BFS [OK]

Hint: Use pop(0) for queue to maintain BFS order [OK]

Common Mistakes:

• Using pop() instead of pop(0) for queue
• Ignoring empty root check
• Incorrect horizontal distance updates

5. You have a binary tree where multiple nodes share the same horizontal distance and depth. How should you modify the bottom view algorithm to always show the node with the greatest depth at each horizontal distance?

hard

A. Store nodes in a list for each horizontal distance and pick the smallest value

B. Store only the first node encountered at each horizontal distance

C. Store both node value and depth in the dictionary, update only if new node depth is greater

D. Ignore depth and update dictionary with last visited node

Solution

1. Step 1: Understand the need to track depth

   To show the bottom-most node at each horizontal distance, we must know which node is deepest (greatest depth).

2. Step 2: Modify dictionary to store value and depth

   Store a tuple (node value, depth) for each horizontal distance. Update only if new node's depth is greater than stored depth.

3. Final Answer:

   Store both node value and depth in the dictionary, update only if new node depth is greater -> Option C

4. Quick Check:

   Track depth to update bottom view nodes correctly [OK]

Hint: Track depth with node to update bottom view correctly [OK]

Common Mistakes:

• Ignoring depth and overwriting nodes incorrectly
• Storing all nodes without filtering by depth
• Picking first or last node without depth check