Top view of binary tree

You all are already familiar with the binary tree data structure, but did you know how the Top view of the binary tree looks likes? If not, then, you come to the right place.

So, in this blog, you will get to know about the Top view of binary tree and how we can code to get the Top view of binary tree.

Let’s start the blog.

Understand the Binary Tree Data Structure:

Before delving into the top view of the binary tree, let’s briefly understand the basics of binary trees to get an understanding of what the top view is actually like. 

So, a binary tree is a hierarchical data structure in which each node has at most two children that are the left child node and the right child node. 

• The topmost node of the binary tree is called as root.
• Nodes with no children in the binary tree are called leaf nodes. 
• The intermediate nodes between the root node and the leaf node are internal nodes.
• Each internal node connects to its children through edges.  

So, the binary tree is a very important and useful data structure that follows a specific approach and makes it suitable for various applications, such as data storage, searching, and sorting.

And to know deeper about binary trees, you can read this article.

What is the top view of a binary tree?

So, the top view of binary tree is a unique way of visualizing the tree’s structure from the top side, as if a user looking down upon the binary tree. 

Imagine that you are standing on the root node and observing the tree from above. You can see only one node at each horizontal distance from the root, not the inner nodes. So, the nodes which are visible to you come in the top view of the binary tree.

So, if you look at the above binary tree from the root node, then we can clearly see that only nodes 1, 2, 3, 4 and 7 are visible to us.

So, the Top view of this binary tree is 4,2,1,3 and 7.

How to construct the top view of a binary tree?

So, to construct the top view of binary tree, we just need to perform a breadth-first traversal and keep in mind to maintain the horizontal distance of each node from the root in the binary tree. 

Also, during the traversal, we keep track of the first node we see at each new horizontal distance. 

How to print top view of a binary tree?

Here is the code to find the top view of a binary tree in C++. 

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

using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int value){
        val=value;
        left=NULL;
        right=NULL;
    }
};

// Function to perform the top view of a binary tree
void topView(TreeNode* root) {
    if (!root)
        return;

    // Create a map to store the nodes at each horizontal distance (HD) from the root
    map<int, int> topViewMap;

    // Create a queue to perform level-order traversal
    queue<pair<TreeNode*, int>> q;
    q.push(make_pair(root, 0));

    while (!q.empty()) {
        TreeNode* node = q.front().first;
        int hd = q.front().second;
        q.pop();

        // Store the first node encountered at each horizontal distance in the map
        if (topViewMap.find(hd) == topViewMap.end()) {
            topViewMap[hd] = node->val;
        }

        // Enqueue the left child with HD - 1 and right child with HD + 1
        if (node->left)
            q.push(make_pair(node->left, hd - 1));
        if (node->right)
            q.push(make_pair(node->right, hd + 1));
    }

    // Print the nodes in the top view from the map
    for (const auto& entry : topViewMap) {
        cout << entry.second << " ";
    }
}

int main() {
    // Example binary tree: (same as shown in the previous explanation)
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->left->left = new TreeNode(8);
    root->left->left->right = new TreeNode(9);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right= new TreeNode(7);

    cout << "Top view of the binary tree: ";
    topView(root);

    return 0;
}

So, let’s start with the explanation:

1. We will start by defining the “TreeNode” structure that represents a single node in the binary tree. And each node of a tree contains a value and two pointers to its left and right child node.

2. Then, we make the “topView” function which is responsible for finding and printing the top view of the binary tree. Every time it takes the root node as its input.

3. So, inside the “topView” function, we have to create a map<int, int> topViewMap field to store all the nodes at each horizontal row of the binary tree from the root. Here, the key of the map data structure represents the horizontal distance, and the value inside it represents the value of the node.

4. Next, we will also create a queue<pair<TreeNode*, int>> as a q variable to perform level-order traversal one by one. And each element in the queue has a pair that consists of the node and its horizontal distance from the root node of the binary tree.

5. After this, we initialize the traversal by enqueuing the root node with a horizontal distance of 0 into the queue.

6. While the queue is not empty, we will dequeue the front element and store it in variables “node” and “hd”.

7. Then, we will check if the “hd” var exists as a key in the “topViewMap” or not. If not, we insert the current node’s value as the value for the “hd” key in the map. And this will ensure that we store the first node encountered at each unique horizontal distance.

8. We then enqueue the left child of the current node with “hd – 1” and the right child with “hd + 1” into the queue to continue traversing the tree.

9. Once the traversal is complete, the “topViewMap” will have the nodes in the top view of the binary tree.

10. Finally, we loop through the “topViewMap” and print the values (nodes) in the top view in the correct order.

Output: Top view of the binary tree: 8 4 2 1 3 7 

Conclusion:

In conclusion, we can say that the top view of binary tree provides a very unique perspective when we see the binary tree from the root node. It also allows us to see the nodes that are visible from the top viewpoint at each unique horizontal distance. 

Also, this data structure is useful in various scenarios like during visualization, data analysis and many more.