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 bottom view of the following binary tree after running the given code?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

#include <iostream>
#include <map>
#include <queue>

void bottomView(Node* root) {
    if (!root) return;
    std::map<int, int> hdNodeMap; // horizontal distance -> node data
    std::queue<std::pair<Node*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* node = p.first;
        int hd = p.second;
        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) {
        std::cout << it.second << " ";
    }
}

int main() {
    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->left = new Node(4);
    root->right->right = new Node(25);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);
    bottomView(root);
    return 0;
}

A 5 8 10 14 25

B 5 8 3 14 25

C 5 10 3 14 25

D 5 10 4 14 25

💡 Hint

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

The bottom view prints the last node encountered at each horizontal distance during level order traversal.

Horizontal distances and nodes are:

• -2: 5
• -1: 10
• 0: 4
• 1: 14
• 2: 25

So output is: 5 10 4 14 25

🧠 Conceptual

intermediate

Horizontal Distance in Bottom View

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

A The distance of the node from the root measured horizontally, left is negative, right is positive

B The vertical level of the node in the tree

C The depth of the node from the root

D The number of nodes in the subtree rooted at that node

💡 Hint

Think about how nodes are positioned relative to the root when viewed from the side.

Horizontal distance is the relative horizontal position of a node from the root.

Root has HD 0, left child HD -1, right child HD +1, and so on.

🔧 Debug

advanced

Identify the Bug in Bottom View Implementation

What is the bug in the following bottom view code snippet?

DSA C++

void bottomView(Node* root) {
    if (!root) return;
    std::map<int, int> hdNodeMap;
    std::queue<std::pair<Node*, int>> 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) {
        std::cout << it.second << " ";
    }
}

A It does not check for null nodes before pushing to queue

B It uses a queue instead of a stack, causing wrong traversal order

C It only stores the first node at each horizontal distance, not the bottom-most node

D It uses map which does not maintain order of horizontal distances

💡 Hint

Bottom view should show the last node at each horizontal distance, not the first.

The code stores the node data only if the horizontal distance is not already in the map.

This means it keeps the first node encountered at that horizontal distance during level order traversal.

But bottom view requires the last node at that horizontal distance, so the map should be updated every time.

❓ Predict Output

advanced

Bottom View Output for Unbalanced Tree

What is the output of the bottom view function for this unbalanced binary tree?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

#include <iostream>
#include <map>
#include <queue>

void bottomView(Node* root) {
    if (!root) return;
    std::map<int, int> hdNodeMap;
    std::queue<std::pair<Node*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* node = p.first;
        int hd = p.second;
        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) {
        std::cout << it.second << " ";
    }
}

int main() {
    Node* root = new Node(1);
    root->right = new Node(2);
    root->right->right = new Node(5);
    root->right->right->left = new Node(3);
    root->right->right->right = new Node(6);
    root->right->right->left->left = new Node(4);
    bottomView(root);
    return 0;
}

A 4 3 5 6

B 1 2 3 5 6

C 1 2 5 3 6

D 1 2 5 4 6

💡 Hint

Track horizontal distances carefully for each node.

Horizontal distances and nodes:

• 0: 4
• 1: 3
• 2: 5
• 3: 6

Bottom view prints nodes in order of HD: 4 3 5 6

🧠 Conceptual

expert

Why Use Level Order Traversal for Bottom View?

Why is level order traversal (BFS) preferred over DFS for computing the bottom view of a binary tree?

A Because DFS cannot track horizontal distances correctly

B Because BFS processes nodes level by level ensuring the bottom-most nodes overwrite previous ones at the same horizontal distance

C Because BFS uses less memory than DFS in all cases

D Because DFS visits nodes in random order which is unsuitable for bottom view

💡 Hint

Think about how nodes at the same horizontal distance but different depths are processed.

BFS visits nodes level by level, so nodes at lower levels overwrite nodes at higher levels for the same horizontal distance.

This ensures 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 visible when looking from the bottom of the tree, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

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

3. Final Answer:

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

4. Quick Check:

   Bottom view = nodes visible from bottom [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 of the following C++ STL containers is most suitable to store nodes by their horizontal distance for bottom view calculation?

easy

A. std::vector<int>

B. std::map

C. std::stack<int>

D. std::queue<int>

Solution

1. Step 1: Identify data structure needs

   We need to map horizontal distances (int) to node values (int) and keep them sorted by horizontal distance.

2. Step 2: Choose container

   std::map keeps keys sorted and allows key-value pairs, perfect for horizontal distance mapping.

3. Final Answer:

   std::map -> Option B

4. Quick Check:

   Use map for sorted key-value pairs [OK]

Hint: Use map to keep horizontal distances sorted [OK]

Common Mistakes:

• Using vector which is index-based, not key-based
• Using stack or queue which don't map keys to values
• Not sorting horizontal distances

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

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

medium

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

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

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

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

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root 20 at HD=0; 8 at HD=-1; 22 at HD=1; 5 at HD=-2; 3 at HD=0; 25 at HD=2; 10 at HD=-1; 14 at HD=1.

2. Step 2: Determine bottom view nodes by HD

   At HD=-2: 5; HD=-1: 10 (lower than 8); HD=0: 3 (lower than 20); HD=1: 14 (lower than 22); HD=2: 25.

3. Final Answer:

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

4. Quick Check:

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

Hint: Track horizontal distances and pick lowest nodes [OK]

Common Mistakes:

• Choosing top nodes instead of bottom nodes
• Mixing horizontal distances incorrectly
• Ignoring nodes at same horizontal distance but lower level

4. Consider this code snippet for bottom view calculation. What is the error?

void bottomView(Node* root) {
  if (!root) return;
  std::map hdNodeMap;
  std::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) {
    std::cout << it.second << " ";
  }
}

medium

A. It stores only the first node at each horizontal distance, not the bottom-most

B. It uses queue incorrectly for BFS traversal

C. It does not check for null root

D. It prints nodes in reverse horizontal order

Solution

1. Step 1: Analyze node storage logic

   The code stores node data only if horizontal distance is not already in map, so it keeps first node encountered at that HD.

2. Step 2: Understand bottom view requirement

   Bottom view requires the lowest node at each HD, so we must update map with nodes at lower levels, not just first.

3. Final Answer:

   It stores only the first node at each horizontal distance, not the bottom-most -> Option A

4. Quick Check:

   Bottom view needs last node at HD, not first [OK]

Hint: Update map with latest node at each horizontal distance [OK]

Common Mistakes:

• Not updating map for lower level nodes
• Assuming BFS order guarantees bottom view
• Ignoring horizontal distance updates

5. Given a binary tree, how would you modify the bottom view algorithm to handle nodes with the same horizontal distance and depth, ensuring the rightmost node is chosen in the bottom view?

hard

A. Use a queue for BFS and update map only if node depth is greater, replacing existing node

B. Use DFS and store only the first node encountered at each horizontal distance

C. Use a stack and update map only if node depth is less than current stored depth

D. Use BFS and update map only if node depth is greater or equal, replacing existing node

Solution

1. Step 1: Understand the problem with same HD and depth

   When nodes share horizontal distance and depth, bottom view should show the rightmost node.

2. Step 2: Modify BFS approach

   Use BFS to traverse level by level, and update map if current node's depth is greater or equal to stored node's depth, ensuring rightmost node replaces leftmost at same depth.

3. Step 3: Implement depth tracking

   Track depth along with horizontal distance, update map accordingly during BFS.

4. Final Answer:

   Use BFS and update map only if node depth is greater or equal, replacing existing node -> Option D

5. Quick Check:

   Update map on equal or greater depth for rightmost node [OK]

Hint: Update map if depth >= current to keep rightmost node [OK]

Common Mistakes:

• Ignoring depth when updating map
• Using DFS which doesn't guarantee level order
• Not handling equal depth nodes properly