Bottom view of the binary tree in C++

In this tutorial, we will learn about the bottom view of the binary tree in C++. We will also see the code implementation to print the bottom view of the binary tree.

We will see examples to understand the concept in a better way.

Bottom view of the binary tree

The bottom view of the binary tree is a set of nodes visible when we see the tree from bottom. Any node x is there in output if x is the bottommost node at its horizontal distance. The horizontal distance of left child of a node x is equal to a horizontal distance of x minus 1, and that of the right child is the horizontal distance of x plus 1.

You can also learn: Right view of the binary tree in C++




Top view of binary tree in C++

Let,s see the examples,

                        1
                      /   \
                    2      6
                     \   /   \
                      3 7     9     bottom view of tree is 4-7-8-9.
                    /  \ \ 
                   4    5 8 

                        1
                      /   \
                    2      3
                  /  \   /   \
                4     5 6     7     bottom view of tree is 4-2-6-3-7.

So, we can see the bottom view of the binary tree in above examples.

We can use the level order traversal to print the bottom view of the binary tree.

Now, Let’s see the pseudo code,

1.Build a structure 
     struct bottom{
         Node* temp;
         int hd;
     };
2.Take an empty map-- map<int,int>m;
3.Take an empty queue--queue<Node*>q.
4.Push the root node into queue with hd=0.
5.While q is not empty
     -Pop the node from queue.
     -update m[pop node.hd]=node->data.
     -Push the left child in queue with hd=hd-1.
     -Push the right child in queue with hd=hd+1.
6.Traverse the map for print the stored node value.

Now, let’s see the code.

Code implementation in c++

 

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

struct Node{
  int data;
  Node* left;
  Node* right;
};
//function to create node
Node* create(int x){
  Node* temp=(Node*)malloc(sizeof(Node));
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//function to find the bottom view
struct bottom{
       Node* temp;
       int hd;
   };
void bottomView(Node *root)
{
   bottom p;
   queue<bottom>q;
   map<int,int>m;
   map<int,int>::iterator it;
   p.temp=root;
   p.hd=0;
   q.push(p);
   while(!q.empty()){
       bottom pnode=q.front();q.pop();
       m[pnode.hd]=(pnode.temp)->data;
       if((pnode.temp)->left){
           bottom node;
           node.temp=(pnode.temp)->left;
           node.hd=(pnode.hd)-1;
           q.push(node);
       }
       if((pnode.temp)->right){
           bottom node;
           node.temp=(pnode.temp)->right;
           node.hd=(pnode.hd)+1;
           q.push(node);
       }
   }
   for(it=m.begin();it!=m.end();it++){
       cout<<it->second<<" ";
   }
}
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(3);
  root->left->right->left=create(4);
  root->left->right->right=create(5);
  root->right=create(6);
  root->right->left=create(7);
  root->right->left->right=create(8);
  root->right->right=create(9);
    cout<<"bottom view of the given tree is: "<<endl;
    bottomView(root);
    return 0;
}

Output

bottom view of the given tree is:
4 7 8 9

We hope you have understood “Bottom view of a binary tree in C++”.

You may also learn,

Boundary traversal of the Binary tree in C++

Find out the Diameter of the Binary Tree in C++


Leave a Reply

Your email address will not be published. Required fields are marked *