Top view of binary tree

We know that a binary tree is a kind of tree that helps us organize our tree and that it is a kind of non-linear info structure that at least contains two nods or child. It has bi in its name, which means two of anything. The various operations in the binary tree help us in maintaining the order of the tree without disbalancing the height or arrangement of the binary tree.

In this article, we are mainly going to discuss the top view of the binary tree. The top view of the binary tree is the combination of the nods that are visible to us when we are introspecting the tree from the topmost side. We can also print the top view of the binary tree, and the presented output can be printed in any given order.

Implementation

#include <iostream>
#include <map>
using namespace std;
 
// Implementing info structure to store a binary tree nod
struct Nod
{
    int ky;
    Nod *lft, *rt;
 
    Nod(int ky)
    {
        this->ky = ky;
        this->lft = this->rt = NILLpointer;
    }
};
 
//Creating a function to perform the pre-order traversal on the binary tree.
// the node in the tree contains the horizontal dtance ‘dt’ from the tree root.  
// the levels present in the tree represent the node’s ls.
void printTp(Nod* root, int dt, int l, auto &map)
{
    // Case1: when the tree is empty
    if (root == NILLpointer) {
        return;
    }
 
    //you can update the map in the following cases, either when the current level is less than the max level or when the horizontal dtance is visible for the first time.
    if (map.find(dt) == map.end() || l < map[dt].second)
    {
        // we have to update the value and distance for the current level
        map[dt] = { root->ky, l };
    }
 
    //rearrange for the left subtree as the horizontal distance is decreasing and the levels are increasing by 1. 
    printTp(root->lft, dt - 1, l + 1, map);
 
    //rearrange for the right subtree as the horizontal distance is decreasing and the levels are increasing by 1. 
    printTp(root->rt, dt + 1, l + 1, map);
}
 //declaring a function to get the top view of the binary tree.
void printTp(Nod* root)
{
    // create an empty map where
    // ky —> relative horizontal dtance of the nod from the root nod, and
    // value —> p containing the nod's value and its l
    map<int, p<int, int>> map;
 
    // perform pre-order traversal on the tree and fill the map
    printTp(root, 0, 0, map);
 
    // traverse the map and print the top view
    for (auto it: map) {
        cout << it.second.first << " ";
    }
}
 
int main()
{
    Nod* root = new Nod(1);
    root->lft = new Nod(2);
    root->rt = new Nod(3);
    root->lft->rt = new Nod(4);
    root->rt->lft = new Nod(5);
    root->rt->rt = new Nod(6);
    root->rt->lft->lft = new Nod(7);
    root->rt->lft->rt = new Nod(8);
 
    printTp(root);
 
    return 0;
}

Output:

Example 2)

// C++ program to print top

// view of binary tree

#include <bits/stdc++.h>
using namespace std;


// Structure of the binary tree
struct Nod {
	Nod* lft;
	Nod* rt;
	int h;
	int info;
};


// creating a function to make a new node
Nod* newNod(int ky)
{
	Nod* nod = new Nod();
	nod->lft = nod->rt = NILL;
	nod->info = ky;
	return nod;
}


// declaring a function that should print the top view of the binary tree.
void topview(Nod* root)
{
	if (root == NILL)
		return;
	queue<Nod*> c;
	map<int, int> n;
	int h = 0;
	root->h = h;


	// We have to push the node and horizontal distance into the queue.
	c.push(root);


	cout << "The top view of the tree is : \n";


	while (c.size()) {
		h = root->h;


		//the function will return the value 1 if the container occupies an element whose key is equal to the horizontal distance and returns 0 in all the other cases. 
		if (n.count(h) == 0)
			n[h] = root->info;
		if (root->lft) {
			root->lft->h = h - 1;
			c.push(root->lft);
		}
		if (root->rt) {
			root->rt->h = h + 1;
			c.push(root->rt);
		}
		c.pop();
		root = c.front();
	}


	for (auto i = n.begin(); i != n.end(); i++) {
		cout << i->second << " ";
	}
}


// Driver code
int main()
{
	/* Create the following Binary Tree
		1
		/ \
	2 3
		\
		4
		\
			5
			\
			6
	*/
	Nod* root = newNod(1);
	root->lft = newNod(2);
	root->rt = newNod(3);
	root->lft->rt = newNod(4);
	root->lft->rt->rt = newNod(5);
	root->lft->rt->rt->rt = newNod(6);
	cout << "Following are nods in top view of Binary "
			"Tree\n";
	topview(root);
	return 0;
}

Output: