Bottom View of Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the output of the bottom view traversal for the given binary tree?

DSA C

/* Binary Tree Structure:
       20
      /  \
     8   22
    / \    \
   5  3    25
     / \    
    10 14
*/

// Bottom view prints nodes visible when the tree is viewed from the bottom.
// Expected output format: node values from left to right as a list.

// Assume horizontal distance (hd) from root: root=0, left=-1, right=+1, etc.

// Bottom view nodes: 5, 10, 3, 14, 25

// Output: [5, 10, 3, 14, 25]

A [20, 8, 3, 14, 25]

B [5, 8, 3, 14, 25]

C [5, 10, 3, 14, 25]

D [5, 10, 8, 14, 25]

💡 Hint

Consider the horizontal distance of each node and which node is the lowest at that distance.

The bottom view shows the last node at each horizontal distance when viewed from bottom.

At hd=-2: 5

At hd=-1: 10 (overwrites 8 because 10 is lower)

At hd=0: 3 (overwrites 20)

At hd=1: 14

At hd=2: 25

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Bottom View

In the bottom view of a binary tree, what does the horizontal distance (hd) represent?

A The vertical level of a node from the root

B The horizontal position of a node relative to the root

C The depth of a node in the tree

D The number of children a node has

💡 Hint

Think about how nodes are positioned left or right relative to the root.

Horizontal distance (hd) measures how far left or right a node is from the root node.

Root has hd=0, left child hd=parent hd - 1, right child hd=parent hd + 1.

🔧 Debug

advanced

Identify the Error in Bottom View Implementation

What error will this C code produce when computing the bottom view of a binary tree?

DSA C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void bottomView(struct Node* root) {
    if (!root) return;
    int hd = 0;
    // Missing data structure to store nodes by hd
    bottomView(root->left);
    printf("%d ", root->data);
    bottomView(root->right);
}

int main() {
    struct Node* root = malloc(sizeof(struct Node));
    root->data = 1;
    root->left = NULL;
    root->right = NULL;
    bottomView(root);
    return 0;
}

A The code prints nodes in inorder but does not compute bottom view correctly

B Compilation error due to missing semicolon

C Infinite recursion causing stack overflow

D Runtime error due to null pointer dereference

💡 Hint

Check if the code uses any data structure to track horizontal distances.

The code performs an inorder traversal and prints nodes but does not track horizontal distances or levels.

Bottom view requires tracking nodes by horizontal distance and choosing the lowest node at each distance.

🚀 Application

advanced

Bottom View of a Complex Binary Tree

Given the binary tree below, what is the bottom view output? /* Tree structure: 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 */

A [4, 2, 6, 8, 7, 9]

B [4, 2, 5, 8, 7, 9]

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

D [4, 2, 6, 8, 3, 9]

💡 Hint

Calculate horizontal distances and pick the lowest node at each distance.

Horizontal distances and bottom nodes:

• hd=-2: 4
• hd=-1: 2
• hd=0: 6 (overwrites 1 and 5)
• hd=1: 8
• hd=2: 7
• hd=3: 9

🧠 Conceptual

expert

Why Use a Queue and Map in Bottom View Algorithm?

In an efficient bottom view algorithm for a binary tree, why do we use a queue and a map (or dictionary)?

A Queue stores nodes in preorder; map stores nodes in inorder

B Queue stores nodes sorted by value; map stores node depths

C Queue is used for recursive calls; map stores parent nodes

D Queue helps in level order traversal; map stores the last node at each horizontal distance

💡 Hint

Think about how to visit nodes level by level and track horizontal distances.

The queue supports level order traversal to visit nodes breadth-first.

The map stores the most recent node at each horizontal distance, ensuring the bottom-most node is recorded.

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