{"post":"

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>\r\nusing namespace std;\nstruct Node{\r\nint data;\r\nNode* left;\r\nNode* right;\r\nNode(int data){\r\nthis->data = data;\r\nleft = right = NULL;\r\n}\r\n};
\nvoid printTopBottomViewIterative(Node* root){\r\nif(root == NULL) return;
\n  map&lt;int, vector&lt;Node*&gt;&gt; mp;\r\n  queue&lt;pair&lt;Node*,int&gt;&gt; q;\r\n  q.push({root,0});\r\n\r\n  while(!q.empty()){\r\n      int size = q.size();\r\n      for(int i = 0; i &lt; size; i++){\r\n          Node* curr = q.front().first;\r\n          int verLevel = q.front().second;\r\n          q.pop();\r\n          mp[verLevel].push_back(curr);\r\n          if(curr-&gt;left) q.push({curr-&gt;left, verLevel - 1});\r\n          if(curr-&gt;right) q.push({curr-&gt;right, verLevel + 1});\r\n      }\r\n\r\n  }\r\n\r\n  for(auto i:mp){\r\n      //cout&lt;&lt;i.second[0]-&gt;data&lt;&lt;\" \"; //top view\r\n      cout&lt;&lt;i.second[i.second.size() - 1]-&gt;data&lt;&lt;\" \"; //bottom view\r\n  }\n
\n}
\nint main() {\r\n/*\r\n1\r\n/    
\n2      3\r\n/   \\   /  
\n4     5 6    7\r\n/\r\nstruct Node root = new Node(1);\r\nroot->left = new Node(2);\r\nroot->left->left = new Node(4);\r\nroot->left->right = new Node(5);\r\nroot->right = new Node(3);\r\nroot->right->left = new Node(6);\r\nroot->right->right = new Node(7);\r\nprintTopBottomViewIterative(root);\r\nreturn 0;\r\n}

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>\r\nusing namespace std;\nstruct Node{\r\nint data;\r\nNode* left;\r\nNode* right;\r\nNode(int data){\r\nthis->data = data;\r\nleft = right = NULL;\r\n}\r\n};
\nmap<int, Node*> mapp;\r\nvoid printTopBottomViewRecursively(Node* root, int state){\r\nif(!root) return;
\nif(mapp.count(state) == 0) mapp[state] = root; //top view\r\n//mapp[state] = root; //bottom view\r\n\r\nprintTopBottomViewRecursively(root-&gt;left, state - 1);\r\nprintTopBottomViewRecursively(root-&gt;right, state + 1);\n
\n}
\nint main() {\r\n/*\r\n1\r\n/    
\n2      3\r\n/   \\   /  
\n4     5 6    7\r\n/\r\nstruct Node root = new Node(1);\r\nroot->left = new Node(2);\r\nroot->left->left = new Node(4);\r\nroot->left->right = new Node(5);\r\nroot->right = new Node(3);\r\nroot->right->left = new Node(6);\r\nroot->right->right = new Node(7);\r\nprintTopBottomViewRecursively(root, 0);\r\nfor(auto i:mapp){\r\ncout<<i.second->data<<\" \";\r\n}\r\nreturn 0;\r\n}

\n","title":"Top view and Bottom view of Binary Tree","authorDetails":{"name":"studymite","slug":"admin"},"description":"We will print top view and bottom view of a binary tree using queue and a map. Using recursion and iteration.","slug":"top-view-and-bottom-view-of-binary-tree/","articleId":"636a83417bb1ce5072622b03","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}