Why Bottom View of Binary Tree in DSA C?

The Big Idea

Discover how to see the hidden bottom view of a tree without guesswork!

The Scenario

Imagine you have a tall tree in your backyard. You want to see which branches are visible if you look at the tree from the bottom, but you only have a photo from the front. Trying to guess which branches you can see from the bottom by looking at the front photo is tricky and confusing.

The Problem

Manually figuring out the bottom view means checking every branch and guessing if it is blocked by others. This is slow and easy to get wrong, especially if the tree is big and has many branches overlapping each other.

The Solution

The bottom view of a binary tree uses a smart way to track which nodes are visible from the bottom by using their horizontal positions. It automatically finds the lowest nodes at each horizontal position, so you get the exact view without guessing.

Before vs After

✗ Before

void printBottomView(Node* root) {
    // Manually check nodes and guess visibility
    // No clear method, lots of nested loops
}

✓ After

void printBottomView(Node* root) {
    // Use horizontal distance and map to track bottom nodes
    // Print nodes from leftmost to rightmost
}

What It Enables

This lets you quickly and correctly see the bottom view of any binary tree, no matter how complex it is.

Real Life Example

In city planning, imagine buildings as nodes in a tree. The bottom view helps find which buildings are visible from street level when looking from the bottom, helping design better layouts.

Key Takeaways

Manual guessing of bottom view is slow and error-prone.

Bottom view uses horizontal distances to find visible nodes from bottom.

This method works efficiently for any binary tree size or shape.

Practice

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

easy

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

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 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 angles, 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 A

4. Quick Check:

   Bottom view = nodes visible from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal position [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking it shows all leaf nodes only
• Mixing bottom view with side views

2. Which data structure is commonly used to track nodes and their horizontal distances for bottom view calculation?

easy

A. Stack

B. Hash Map (Dictionary)

C. Linked List

D. Queue

Solution

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

   To find the bottom view, we map each node's horizontal distance to its value, updating with the lowest node at that distance.

2. Step 2: Choose the suitable data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, allowing quick updates and lookups.

3. Final Answer:

   Hash Map (Dictionary) -> Option B

4. Quick Check:

   Use hash map to map horizontal distance to node [OK]

Hint: Use hash map to store horizontal distance and node value [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 lookups

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

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

Options show node values from left to right in bottom view.

medium

A. [2, 4, 6, 7]

B. [2, 4, 6, 3, 7]

C. [2, 4, 6, 5, 7]

D. [1, 2, 4, 6, 7]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Assign horizontal distances: 1=0, 2=-1, 3=1, 4=0, 5=2, 6=1, 7=3. Bottom nodes at each distance are: -1:2, 0:4, 1:6, 2:5, 3:7.

2. Step 2: Collect bottom view nodes from left to right

   From leftmost (-1) to rightmost (3), nodes are 2, 4, 6, 5, 7.

3. Final Answer:

   [2, 4, 6, 5, 7] -> Option C

4. Quick Check:

   Bottom view nodes left to right = [2, 4, 6, 5, 7] [OK]

Hint: Track horizontal distances and pick last node at each [OK]

Common Mistakes:

• Including nodes not visible from bottom
• Confusing horizontal distances
• Listing nodes in wrong order

4. Identify the error in this C code snippet for bottom view calculation:

void bottomView(Node* root) {
    map hdNodeMap;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (hdNodeMap.find(hd) == hdNodeMap.end()) {
            hdNodeMap[hd] = node->data;
        }
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : hdNodeMap) {
        cout << it.second << " ";
    }
}

medium

A. Output loop should print keys instead of values

B. Queue is not initialized properly

C. Left and right child checks are reversed

D. Using map prevents updating bottom nodes at same horizontal distance

Solution

1. Step 1: Analyze map usage for horizontal distances

   The code inserts node data only if horizontal distance is not present, so it keeps the first node seen, which is top view behavior.

2. Step 2: Correct approach for bottom view

   For bottom view, update the map every time a node at the same horizontal distance is found, so the last node at that distance remains.

3. Final Answer:

   Using map prevents updating bottom nodes at same horizontal distance -> Option D

4. Quick Check:

   Bottom view needs updating map entries [OK]

Hint: Update map for every node at horizontal distance for bottom view [OK]

Common Mistakes:

• Using if condition to insert only once (top view logic)
• Not updating map with lower nodes
• Confusing top and bottom view logic

5. Given a binary tree where multiple nodes share the same horizontal distance and level, 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 that appears first in level order traversal at that horizontal distance

C. Show the node with the smallest value at that horizontal distance

D. Show the node with the largest value at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the last node encountered in level order at that position.

2. Step 2: Use level order traversal order to decide

   Level order traversal visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones in the map.

3. Final Answer:

   Show the node that appears last in level order traversal at that horizontal distance -> Option A

4. Quick Check:

   Bottom view picks last node at horizontal distance [OK]

Hint: Last node at horizontal distance in level order is bottom view node [OK]

Common Mistakes:

• Picking first node instead of last
• Choosing node by value instead of position
• Ignoring traversal order impact