{"id":2644,"date":"2021-10-13T19:20:00","date_gmt":"2021-10-13T13:50:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2644"},"modified":"2022-07-08T15:27:15","modified_gmt":"2022-07-08T09:57:15","slug":"bottom-view-of-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/bottom-view-of-binary-tree\/","title":{"rendered":"Bottom View of Binary Tree"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#hashmap-and-recursion-approach\">Hashmap and Recursion Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#queue-approach\">Queue Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-queue-method\">C++ Implementation of Queue Method<\/a><\/li><li><a href=\"#java-implementation-of-queue-method\">Java Implementation of Queue Method<\/a><\/li><li><a href=\"#python-implementation-of-queue-method\">Python Implementation of Queue Method<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given a binary tree of integers. The task is to return an array of integers representing the bottom view of the Binary tree.<\/p>\n\n\n\n<p>Bottom view of a Binary Tree: is a set of nodes visible when the tree is visited from the bottom.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"538\"  height=\"435\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"input\"  class=\"wp-image-2731 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 538px) 100vw, 538px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input.png 538w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-300x243.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-380x307.png 380w\" ><\/figure>\n\n\n\n<p><strong>Output: <\/strong>[8, 4, 9, 5, 3, 7]<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"686\"  height=\"541\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Output Explanation\"  class=\"wp-image-2732 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 686px) 100vw, 686px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output.png 686w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-300x237.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-380x300.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-550x434.png 550w\" ><\/figure>\n\n\n\n<p><strong>Input:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"446\"  height=\"352\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Input\"  class=\"wp-image-2733 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 446px) 100vw, 446px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-1.png 446w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-1-300x237.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/input-1-380x300.png 380w\" ><\/figure>\n\n\n\n<p><strong>Output:<\/strong> [1, 3, 2]\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"hashmap-and-recursion-approach\">Hashmap and Recursion Approach<\/h2>\n\n\n\n<p>The bottom view of a binary tree refers to the bottommost nodes present at the same level.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Perform a preorder traversal to calculate the level of each node of the binary tree.<\/li><li>Consider a hashmap and store the height into the map, where the <strong>key<\/strong> is the level or the horizontal distance of the <strong>ith <\/strong>node and the value is a pair <strong>(p, q)<\/strong>, where <strong>p<\/strong> is the value of the node and <strong>q<\/strong> is the height of the node.<\/li><li>For every node:<ul><li>Add the node to the resultant map if it is the first node to have the current horizontal distance.<\/li><li>Else, if a node is already present for the particular distance, replace the previous node with the current node, if the node has a height greater than the previous node.<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void bottomview(Tree * root, map&lt;int,vector&lt;int>>&amp; m, int lev, int h_dist){\n if (root == NULL)\n   return;\n \n if (m.find(h_dist) == m.end()) {  \n   m[h_dist].push_back(lev);\n   m[h_dist].push_back(root -> data);\n }\n  else {\n   if (m[h_dist][0] &lt;= lev) {\n     m[h_dist][0] = lev;\n     m[h_dist][1]= root -> data;\n   }\n }\n \/\/ Calling the function for the right and left subtrees\n \/\/ with the appropriate parameters.\n bottomview(root -> left, m, lev + 1, h_dist - 1);\n bottomview(root -> right, m, lev + 1, h_dist + 1);\n}\nVoid print_bottom_of_binary_tree(Tree* root){\n   map&lt;int,vector&lt;int>> Map;\n   bottomview(root, Map, 1, 0);\n   for (auto it = Map.begin(); it != Map.end(); ++it)\n   {\n     cout &lt;&lt; (it-> second)[1]&lt;&lt; \" \";\n   }\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bottomview(Node root, TreeMap&lt;Integer, int[]> m, int curr, int hd)\n{\n    if (root == null)\n        return;\n \n     if (!m.containsKey(hd))\n    {\n        m.put(hd, new int[]{ root.data, curr });\n    }\n    else\n    {\n        int[] p = m.get(hd);\n        if (p[1] &lt;= curr)\n        {\n            p[1] = curr;\n            p[0] = root.data;\n        }\n        m.put(hd, p);\n    }\n    printBottomViewUtil(root.left, curr + 1, hd - 1, m);\n    printBottomViewUtil(root.right, curr + 1,hd + 1, m);\n}\n \nprint_bottom_of_binary_tree(Node root)\n{\n    TreeMap&lt;Integer, int[]> m = new TreeMap&lt;>();\n \n    printBottomViewUtil(root, 0, 0, m);\n    for(int val[] : m.values())\n    {\n        System.out.print(val[0] + \" \");\n    }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def print_bottom_of_binary_tree(root):   \n      d = dict()\n     \n      printBottomViewUtil(root, d, 0, 0)\n      for i in sorted(d.keys()):\n        print(d[i][0], end = \" \")\n \ndef bottomview(root, d, hd, level):\n     if root is None:\n        return\n   \n    if hd in d:\n        if level >= d[hd][1]:\n            d[hd] = [root.data, level]\n    else:\n        d[hd] = [root.data, level]\n         \n    bottomview(root.left, d, hd - 1,level + 1)\n    bottomview(root.right, d, hd + 1,level + 1)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) where N is the number of nodes of the binary tree<strong>.<\/strong><br><strong>Space Complexity:<\/strong> O(N), as a map is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"queue-approach\">Queue Approach<\/h2>\n\n\n\n<p>The approach is to perform a level order traversal of the given binary tree and store them in a queue. Also, consider a map, which stores the horizontal distance of the nodes from root as the key.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise a queue to store the nodes on performing level order traversal.<\/li><li>Push the <strong>root<\/strong> of the binary tree into the queue along with its horizontal distance(<strong>hd)<\/strong>, which is <strong>0.<\/strong><\/li><li>Keep on pushing the left child to the queue along with their horizontal distance as <strong>hd &#8211; 1<\/strong> and <strong>right child <\/strong>&nbsp;as <strong>hd + 1<\/strong>.<\/li><li>While the queue is not empty, perform the following operations:<ul><li>Store the front element of the queue is a variable, say, <strong>res.<\/strong><\/li><li>Pop the element.<\/li><li>Put the dequeued element, stored in <strong>res<\/strong> and update its value in the map.<\/li><li>If a left child is present, push the left child into the queue along with its horizontal distance as <strong>hd &#8211; 1<\/strong>.<\/li><li>If a right child is present, push the right child into the queue along with its horizontal distance as <strong>hd + 1<\/strong>.<\/li><\/ul><\/li><li>Print the values in the map which contains the <strong>bottom <\/strong>key of the binary tree.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-of-queue-method\">C++ Implementation of Queue Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void bottomview(Tree * root){\n    int horizontalDistance = 0;\n    map&lt;int, Tree*> mp;\n    queue&lt;pair&lt;Tree*, int>> q;\n    q.push({root, 0});\n    while (!q.empty()) {\n        pair&lt;BinaryTreeNode&lt;int> *, int> p = q.front();\n        q.pop();\n        mp[p.second] = p.first;\n        if (p.first->left != NULL) {\n            q.push({p.first->left, p.second - 1});\n        }\n        if (p.first->right != NULL) {\n            q.push({p.first->right, p.second + 1});\n        }\n    }\n     \n   for (auto i = mp.begin(); i != mp.end(); i++) {\n        cout &lt;&lt;(i->second->data) &lt;&lt;\u201d \u201c;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation-of-queue-method\">Java Implementation of Queue Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Pair {\n\tTree root;\n\tint level;\n\tPair() {\n\t}\n\tPair(Tree root, int level) {\n\t\tthis.root = root;\n\t\tthis.level = level;\n\t}\n}\n \nbottomView(BinaryTreeNode root) {\n\t\tint horizontalDistance = 0;\n\t\tArrayList&lt;Integer> ans = new ArrayList&lt;>();\n\t\tHashMap&lt;Integer, BinaryTreeNode> mp = new HashMap&lt;>();\n \n\t\tQueue&lt;Pair> q = new LinkedList&lt;>();\n\t\tPair p1 = new Pair(root, 0);\n\t\tq.add(p1);\n\t\twhile (!q.isEmpty()) {\n\t\t\tPair p = q.poll();\n\t\t\tmp.put(p.level, p.root);\n\t\t\tif (p.root.left != null) {\n\t\t\t\tq.add(new Pair(p.root.left, p.level - 1));\n\t\t\t}\n\t\t\tif (p.root.right != null) {\n\t\t\t\tq.add(new Pair(p.root.right, p.level + 1));\n\t\t\t}\n\t\t}\n\t\tArrayList&lt;Integer> bottomView = new ArrayList&lt;>();\n \n\t\tfor (int key : mp.keySet()) {\n\t\t\tbottomView.add(key);\n\t\t}\n\t\tCollections.sort(bottomView);\n\t\tfor (int i : bottomView) {\n\t\t\tSystem.out.print(mp.get(i).val + \u201c \u201c);\n\t\t}\n\t}\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation-of-queue-method\">Python Implementation of Queue Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Pair:\n    \n    def __init__(self, root, level):\n        self.root = root\n        self.level = level\n        \n\t\ndef bottomView(root):\n    horizontalDistance = 0\n    mp = OrderedDict()\n    \n    q = []\n    \n    p1 = Pair(root, 0)\n    q.append(p1)\n    \n    while len(q) > 0:\n        p = q.pop(0)\n        \n        mp[p.level] = p.root\n        \n        if p.root.left is not None:\n            q.append(Pair(p.root.left, p.level - 1))\n            \n        if p.root.right is not None:\n            q.append(Pair(p.root.right, p.level + 1))\n            \n    bottomViewList = []\n    \n    for key in mp.keys():\n        bottomViewList.append(key)\n        \n        \n    bottomViewList.sort()\n    \n    for i in bottomViewList:\n        print(mp.get(i).data, end = \u201c \u201d)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * log N) where N is the number of nodes of the binary tree<strong>.<\/strong><br><strong>Space Complexity:<\/strong> O(N), as a map is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/vertical-order-traversal-of-binary-tree\/\" target=\"_blank\">Vertical Order traversal of Binary Tree<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/right-view-of-binary-tree\/\" target=\"_blank\">Right view of Binary tree<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the left view of a binary tree?<br><\/strong>The set of nodes visible when the tree is visited from the left is the left view of the binary tree.<\/p>\n\n\n\n<p><strong>How do you print the bottom of a binary tree?<br><\/strong>The bottom view of a binary tree can be printed by hashing and level order traversal of the binary tree.<\/p>\n\n\n\n<p><strong>What is the diameter of a binary tree?<br><\/strong>The diameter of a tree is the number of nodes on the longest path between two leaves in the tree<\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/courses\/programming\/tree-data-structure\/binary-tree\/\" target=\"_blank\">Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/top-view-of-binary-tree\/\" target=\"_blank\">Top view of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/diameter-of-a-binary-tree\/\" target=\"_blank\">Diameter of a Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/level-order-traversal\/\" target=\"_blank\">Level Order Traversal of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/inorder-traversal-of-a-binary-tree\/\" target=\"_blank\">Inorder Traversal of a Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/left-view-of-a-binary-tree\/\" target=\"_blank\">Left View of a Binary Tree<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given a binary tree of integers. The task is to return an array of integers representing the bottom&hellip;\n","protected":false},"author":4,"featured_media":2730,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[450],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2644"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2644"}],"version-history":[{"count":8,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2644\/revisions"}],"predecessor-version":[{"id":10290,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2644\/revisions\/10290"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2730"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2644"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2644"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2644"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}