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.