0
0
DSA C++programming~20 mins

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

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Top View Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
Output of Top View for a Simple Binary Tree
What is the output of the top view traversal for the given binary tree?
DSA C++
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Tree structure:
//       1
//      / \
//     2   3
//      \   \
//       4   5

// Top view expected: 2 -> 1 -> 3 -> 5

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

void topView(Node* root) {
    if (!root) return;
    std::map<int, int> topNode;
    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 (topNode.find(hd) == topNode.end()) {
            topNode[hd] = node->data;
        }
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : topNode) {
        std::cout << it.second << " -> ";
    }
    std::cout << "null" << std::endl;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->right = new Node(5);
    topView(root);
    return 0;
}
A4 -> 2 -> 1 -> 3 -> null
B2 -> 1 -> 3 -> 5 -> null
C2 -> 4 -> 1 -> 3 -> 5 -> null
D1 -> 2 -> 3 -> 4 -> 5 -> null
Attempts:
2 left
💡 Hint
Remember top view shows nodes visible from above, one per horizontal distance.
🧠 Conceptual
intermediate
1:00remaining
Horizontal Distance in Top View
In the top view of a binary tree, what does the horizontal distance (hd) represent?
AThe distance of a node from the root measured horizontally, left is negative, right is positive
BThe vertical level of a node from the root
CThe depth of the node in the tree
DThe number of nodes in the subtree rooted at that node
Attempts:
2 left
💡 Hint
Think about how nodes are positioned left or right relative to the root.
🔧 Debug
advanced
1:30remaining
Identify the Bug in Top View Implementation
What error will occur when running this top view code snippet?
DSA C++
void topView(Node* root) {
    if (!root) return;
    std::map<int, int> topNode;
    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;
        topNode[hd] = node->data; // Bug here: overwrites existing
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : topNode) {
        std::cout << it.second << " -> ";
    }
    std::cout << "null" << std::endl;
}
ARuntime error due to null pointer dereference
BCompilation error due to incorrect queue usage
CThe output will show only the last node at each horizontal distance, not the top view
DNo error, output is correct top view
Attempts:
2 left
💡 Hint
Check how the map is updated inside the loop.
🚀 Application
advanced
2:00remaining
Top View of a Complex Binary Tree
Given the binary tree below, what is the top view output? // Tree structure: // 10 // / \ // 5 15 // / \ \ // 3 7 18 // \ / // 4 16 // Expected output format: node values separated by ' -> ' ending with 'null'
A3 -> 5 -> 10 -> 15 -> 18 -> null
B3 -> 4 -> 5 -> 10 -> 15 -> 16 -> 18 -> null
C3 -> 5 -> 7 -> 10 -> 15 -> 18 -> null
D4 -> 5 -> 10 -> 15 -> 18 -> null
Attempts:
2 left
💡 Hint
Remember top view shows the first node at each horizontal distance from left to right.
🧠 Conceptual
expert
1:30remaining
Why Use a Map in Top View Algorithm?
Why is a map (or dictionary) used to store nodes by horizontal distance in the top view algorithm?
ATo store nodes by their depth level instead of horizontal distance
BTo store all nodes at each horizontal distance for later processing
CTo count the number of nodes at each horizontal distance
DTo keep nodes sorted by their horizontal distance for ordered output
Attempts:
2 left
💡 Hint
Think about how the output order is determined.