Bottom view of the binary tree

The bottom of the binary tree is generally defined as the number of nods present in the bottom-most part of the tree. In this article, we will see the implementation of the same and understand its works.

Implementation

// C++ Program to print Bottom View of Binary Tree

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


// Creating a class
struct Nod
{
	int record; 
	int h; //horizontal distance from the node
	Nod *lft, *rt; 


	// Constructor of a tree node
	Nod(int ky)
	{
		record = ky;
		h = INT_MAX;
		lft = rt = NILL;
	}
};
//creating a way that prints the bottom look of the tree.
Void bottomView(Nod *root)
{
	if (root == NILL)
		return;


	// Initialize a variable 'h' with 0
	int h = 0;


	// Creating a tree map that will store the value.
	// sorted on key data
	map<int, int> n;


	// Creating a queue that will store the value of the node's levels.
	queue<Nod *> c;


//creating a horizontal distance and initializing it with the value present in the root node and adding it to the queue.	
	root->h = h;
	c.push(root); // In STL, push() is used enqueue an item


//Creating a loop.
	while (!c.empty())
	{
		Nod *temp = c.front();
		c.pop(); 


		//From the dequeued node, we must take out the horizontal distance for evaluation.
		h = temp->h;


		//whenever we find a similar horizontal distance, we have to replace it on the map immediately.
		n[h] = temp->record;


		//If the node has a left child, we must add it to the queue, and the horizontal distance will become h-1.
		if (temp->lft != NILL)
		{
			temp->lft->h = h-1;
			c.push(temp->lft);
		}


	//If the node has the right child, we must add it to the queue, and the horizontal distance will become h+1.		
		if (temp->rt != NILL)
		{
			temp->rt->h = h+1;
			c.push(temp->rt);
		}
	}


	//Visiting each of the map items using for loop.
	for (auto i = n.begin(); i != n.end(); ++i)
		cout << i->second << " ";
}


// Driver Code
int main()
{
	Nod *root = new Nod(20);
	root->lft = new Nod(8);
	root->rt = new Nod(22);
	root->lft->lft = new Nod(5);
	root->lft->rt = new Nod(3);
	root->rt->lft = new Nod(4);
	root->rt->rt = new Nod(25);
	root->lft->rt->lft = new Nod(10);
	root->lft->rt->rt = new Nod(14);
	cout << "Bottom view of the given binary tree :\n";
	bottomView(root);
	return 0;
}

Output:

Using a different approach towards the same.

Example 2)

// C++ Program to print Bottom View of Binary Tree

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


struct Nod
{
	int record;
	// horizontal distance from the node
	int h;
	Nod * lft, * rt;
	// Constructor from the tree nod
	Nod(int ky)
	{
		record = ky;
		h = INT_MAX;
		lft = rt = NILL;
	}
};


void printBottomViewUtil(Nod * root, int currentent, int h, map <int, pr <int, int>> & n)
{
	if (root == NILL)
		return;
	//By any chance, if the node of the horizontal distance is not present, add it to the map.
	if (n.find(h) == n.end())
	{
		n[h] = make_pr(root -> record, current);
	}
	//Check the height of the nodes from the horizontal distance.	
	else
	{
		pr < int, int > g = n[h];
		if (g.second <= current)
		{
			n[h].second = current;
			n[h].first = root -> record;
		}
	}
	
	printBottomViewUtil(root -> lft, current + 1, h - 1, n);
		printBottomViewUtil(root -> rt, current + 1, h + 1, n);
}


void printBottomView(Nod * root)
{
	//Creating a map that stores horizontal distance from height and records.
	map < int, pr < int, int > > n;
	
	printBottomViewUtil(root, 0, 0, n);
	
	// Prints the values stored by printBottomViewUtil()
	map < int, pr < int, int > > ::iterator it;
	for (it = n.begin(); it != n.end(); ++it)
	{
		pr < int, int > g = it -> second;
		cout << g.first << " ";
	}
}


int main()
{
	Nod * root = new Nod(20);
	root -> lft = new Nod(8);
	root -> rt = new Nod(22);
	root -> lft -> lft = new Nod(5);
	root -> lft -> rt = new Nod(3);
	root -> rt -> lft = new Nod(4);
	root -> rt -> rt = new Nod(25);
	root -> lft -> rt -> lft = new Nod(10);
	root -> lft -> rt -> rt = new Nod(14);
	cout << "Bottom view of the given binary tree :\n";
	printBottomView(root);
	return 0;
}

Output: