Top View of Binary Tree in DSA C++ - Build from Scratch

Top View of Binary Tree

📖 Scenario: Imagine you are working with a tree of buildings in a city. You want to see which buildings are visible when looking from the top. This means you want to find the top view of a binary tree, where each node represents a building.

🎯 Goal: Build a program that finds and prints the top view of a binary tree. The top view shows the nodes visible when the tree is viewed from above, from left to right.

📋 What You'll Learn

Create a binary tree node structure with integer data and left and right pointers

Build a sample binary tree with given nodes

Use a map to track the first node at each horizontal distance from the root

Traverse the tree using level order traversal to find the top view

Print the top view nodes from leftmost to rightmost horizontal distance

💡 Why This Matters

🌍 Real World

Top view of a binary tree helps in understanding visibility problems like city skyline or network coverage from above.

💼 Career

Understanding tree traversals and views is important for software roles involving data structures, graphics, and spatial data processing.

1

Create the Binary Tree Node Structure and Sample Tree

Create a struct called Node with an int data, and two pointers Node* left and Node* right. Then create a binary tree with root node value 1, root's left child 2, root's right child 3, left child's left child 4, and left child's right child 5.

DSA C++

// Define struct Node
// Create root node with value 1
// Create left and right children and their children
// Your code here

Hint

Define a struct with data and pointers. Then create nodes using new Node(value) and link them.

2

Add a Map to Track Horizontal Distances

Include the map and queue headers. Declare a map<int, int> topViewMap to store the first node data at each horizontal distance. Also, declare a queue<pair<Node*, int>> q to perform level order traversal with horizontal distances.

DSA C++

#include 
#include 
#include 
using namespace std;

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

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

    // Declare map and queue for top view
    // Your code here

    return 0;
}

Hint

Use map to store horizontal distance and node data. Use queue for level order traversal.

3

Implement Level Order Traversal to Find Top View

Push the root node with horizontal distance 0 into the queue. While the queue is not empty, pop the front node and horizontal distance. If the horizontal distance is not in topViewMap, insert the node's data. Then push the left child with horizontal distance minus 1 and right child with horizontal distance plus 1 if they exist.

DSA C++

#include 
#include 
#include 
using namespace std;

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

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

    map topViewMap;
    queue> q;

    // Push root with horizontal distance 0
    // While queue not empty, process nodes
    // Your code here

    return 0;
}

Hint

Use a queue to do level order traversal. Track horizontal distance and store first node at each distance.

4

Print the Top View from Left to Right

Use a for loop to iterate over topViewMap and print each node's data separated by spaces.

DSA C++

Hint

Iterate over the map which is sorted by horizontal distance and print the node values.