Top view and Bottom view of Binary Tree

Top view and Bottom view of a Binary Tree – Iterative

To find the top view and bottom view of a binary tree we need to do a vertical order traversal of the given tree.

For that, we’ll assume a vertical line through all nodes. For the root node, the state of that node will be 0 and while going left we’ll decrement the state by 1 and while going right we’ll increment it by 1.

We’ll store these states and their corresponding nodes in an ordered map(because we want to print the view from left to right).

For the top view, we will print the first node in the vector and for the bottom view, we will print the last node of the vector.

#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
void printTopBottomViewIterative(Node* root){
if(root == NULL) return;
  map&lt;int, vector&lt;Node*&gt;&gt; mp;
  queue&lt;pair&lt;Node*,int&gt;&gt; q;
  q.push({root,0});

  while(!q.empty()){
      int size = q.size();
      for(int i = 0; i &lt; size; i++){
          Node* curr = q.front().first;
          int verLevel = q.front().second;
          q.pop();
          mp[verLevel].push_back(curr);
          if(curr-&gt;left) q.push({curr-&gt;left, verLevel - 1});
          if(curr-&gt;right) q.push({curr-&gt;right, verLevel + 1});
      }

  }

  for(auto i:mp){
      //cout&lt;&lt;i.second[0]-&gt;data&lt;&lt;" "; //top view
      cout&lt;&lt;i.second[i.second.size() - 1]-&gt;data&lt;&lt;" "; //bottom view
  }

}
int main() {
/*
1
/    

2      3
/   \   /  

4     5 6    7
/
struct Node root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
printTopBottomViewIterative(root);
return 0;
}

Top view and Bottom view of a Binary Tree – Recursive

We’ll perform a dfs and convert the above code to recursive.

#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};
map<int, Node*> mapp;
void printTopBottomViewRecursively(Node* root, int state){
if(!root) return;
if(mapp.count(state) == 0) mapp[state] = root; //top view
//mapp[state] = root; //bottom view

printTopBottomViewRecursively(root-&gt;left, state - 1);
printTopBottomViewRecursively(root-&gt;right, state + 1);

}
int main() {
/*
1
/    

2      3
/   \   /  

4     5 6    7
/
struct Node root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
printTopBottomViewRecursively(root, 0);
for(auto i:mapp){
cout<<i.second->data<<" ";
}
return 0;
}