{"id":1090,"date":"2025-09-02T12:24:19","date_gmt":"2025-09-02T06:54:19","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1090"},"modified":"2025-09-02T12:24:21","modified_gmt":"2025-09-02T06:54:21","slug":"bottom-view-of-binary-tree","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/bottom-view-of-binary-tree\/","title":{"rendered":"Bottom View of Binary Tree | BFS with Horizontal Distance Mapping"},"content":{"rendered":"\n<p>The <strong>Bottom View of Binary Tree<\/strong> problem asks us to return the set of nodes visible when looking at the binary tree from <strong>below<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Each node has a <strong>horizontal distance (HD)<\/strong> from the root:\n<ul class=\"wp-block-list\">\n<li>Root \u2192 <code>HD = 0<\/code><\/li>\n\n\n\n<li>Left child \u2192 <code>HD - 1<\/code><\/li>\n\n\n\n<li>Right child \u2192 <code>HD + 1<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>For each HD, the <strong>last node encountered during level-order traversal (BFS)<\/strong> is part of the bottom view.<\/li>\n<\/ul>\n\n\n\n<p>We must output the nodes from <strong>leftmost HD to rightmost HD<\/strong>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/bottom-view-of-binary-tree\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Example<\/h3>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: \n      20\n     \/  \\\n    8   22\n   \/ \\     \\\n  5   3     25\n     \/ \\\n    10  14\n\nOutput: [5, 10, 3, 14, 25]\nExplanation: \nFrom the bottom, nodes 5, 10, 3, 14, and 25 are visible.\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">: <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #B5CEA8\">20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">8   22<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #CE9178\">\/ \\     \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #CE9178\">5   3     25<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">10  14<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: [<\/span><span style=\"color: #B5CEA8\">5<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">10<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">14<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">25<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Explanation<\/span><span style=\"color: #D4D4D4\">: <\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">From the bottom, nodes 5, 10, 3, 14, and 25 are visible.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input:\n       1\n      \/ \\\n     2   3\n    \/\n   4\n\nOutput: [4, 2, 3]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">2   3<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">\/<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: [<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition and Approach<\/h2>\n\n\n\n<p>The key idea is similar to <strong>Top View<\/strong>, but instead of taking the <strong>first node<\/strong> at each HD, we take the <strong>last node<\/strong> seen during BFS traversal.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-step approach:<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start with the root at <code>HD = 0<\/code>.<\/li>\n\n\n\n<li>Perform BFS (level-order traversal).<\/li>\n\n\n\n<li>For every node visited, update <code>hd_map[hd] = node.data<\/code>.\n<ul class=\"wp-block-list\">\n<li>This way, the last node seen at each HD will overwrite previous ones.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>After traversal, sort the keys of <code>hd_map<\/code> and return the values.<\/li>\n<\/ol>\n\n\n\n<p>This ensures the bottom-most nodes are captured.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Implementation<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"'''\nclass Node:\n    def __init__(self, val):\n        self.right = None\n        self.data = val\n        self.left = None\n'''\n\nfrom collections import deque\n\nclass Solution:\n    def bottomView(self, root):\n        if not root:\n            return []\n        \n        # dictionary to store last node for each horizontal distance\n        hd_map = {}\n        \n        # queue for BFS -&gt; stores (node, horizontal_distance)\n        q = deque([(root, 0)])\n        \n        while q:\n            node, hd = q.popleft()\n    \n            # overwrite with the last node seen at this HD\n            hd_map[hd] = node.data\n            \n            # add left and right children with updated HD\n            if node.left:\n                q.append((node.left, hd - 1))\n            if node.right:\n                q.append((node.right, hd + 1))\n        \n        # extract results sorted by horizontal distance\n        result = [hd_map[key] for key in sorted(hd_map.keys())]\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #CE9178\">&#39;&#39;&#39;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">class Node:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">    def __init__(self, val):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">        self.right = None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">        self.data = val<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">        self.left = None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #CE9178\">&#39;&#39;&#39;<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> collections <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> deque<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">bottomView<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> root:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># dictionary to store last node for each horizontal distance<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        hd_map = {}<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># queue for BFS -&gt; stores (node, horizontal_distance)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        q = deque([(root, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">)])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> q:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            node, hd = q.popleft()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># overwrite with the last node seen at this HD<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hd_map[hd] = node.data<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># add left and right children with updated HD<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> node.left:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                q.append((node.left, hd - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> node.right:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                q.append((node.right, hd + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># extract results sorted by horizontal distance<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = [hd_map[key] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> key <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">sorted<\/span><span style=\"color: #D4D4D4\">(hd_map.keys())]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Explanation<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>BFS Traversal:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Uses a queue to process nodes level by level.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Horizontal Distance (HD):<\/strong>\n<ul class=\"wp-block-list\">\n<li>Root = <code>0<\/code>, left child = <code>-1<\/code>, right child = <code>+1<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>hd_map:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Unlike <strong>Top View<\/strong>, we overwrite values for each HD to ensure we capture the bottom-most node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Sorting:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Keys are sorted to ensure left-to-right order of the bottom view.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Dry Run<\/h2>\n\n\n\n<p>Input Tree:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"      20\n     \/  \\\n    8   22\n   \/ \\     \\\n  5   3     25\n     \/ \\\n    10  14\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #B5CEA8\">20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">8   22<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #CE9178\">\/ \\     \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #CE9178\">5   3     25<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">10  14<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Step-by-step BFS traversal:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Root (20, HD=0) \u2192 hd_map = {0: 20}<\/li>\n\n\n\n<li>Left (8, HD=-1) \u2192 hd_map = {-1: 8, 0: 20}<\/li>\n\n\n\n<li>Right (22, HD=1) \u2192 hd_map = {-1: 8, 0: 20, 1: 22}<\/li>\n\n\n\n<li>Left child (5, HD=-2) \u2192 hd_map = {-2: 5, -1: 8, 0: 20, 1: 22}<\/li>\n\n\n\n<li>Right child (3, HD=0) \u2192 overwrite \u2192 hd_map = {-2: 5, -1: 8, 0: 3, 1: 22}<\/li>\n\n\n\n<li>Left (10, HD=-1) \u2192 overwrite \u2192 hd_map = {-2: 5, -1: 10, 0: 3, 1: 22}<\/li>\n\n\n\n<li>Right (14, HD=1) \u2192 overwrite \u2192 hd_map = {-2: 5, -1: 10, 0: 3, 1: 14}<\/li>\n\n\n\n<li>Right (25, HD=2) \u2192 hd_map = {-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}<\/li>\n<\/ol>\n\n\n\n<p>Final sorted output: <code>[5, 10, 3, 14, 25]<\/code><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Time and Space Complexity<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>BFS traversal \u2192 O(N)<\/li>\n\n\n\n<li>Sorting keys \u2192 O(K log K), where K = number of unique HDs<\/li>\n\n\n\n<li>Total \u2192 <strong>O(N log K)<\/strong><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Dictionary for storing last nodes \u2192 O(K)<\/li>\n\n\n\n<li>Queue for BFS \u2192 O(N)<\/li>\n\n\n\n<li>Total \u2192 <strong>O(N)<\/strong><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The <strong>Bottom View of Binary Tree<\/strong> problem is efficiently solved using <strong>BFS with horizontal distance mapping<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Unlike <strong>Top View<\/strong>, we overwrite entries at each HD to capture the bottom-most node.<\/li>\n\n\n\n<li>Sorting ensures the correct left-to-right order of nodes.<\/li>\n\n\n\n<li>Runs in <strong>O(N log K)<\/strong> time and <strong>O(N)<\/strong> space.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Bottom View of Binary Tree problem asks us to return the set of nodes visible when looking at the binary tree from below. We must output the nodes from leftmost HD to rightmost HD. Here&#8217;s the [Problem Link] to begin with. Example Example 1 Example 2 Intuition and Approach The key idea is similar<\/p>\n","protected":false},"author":1,"featured_media":1091,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[14,19],"class_list":{"0":"post-1090","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-binary-trees","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/09\/bottom-view-of-binary-tree-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1090","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1090"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1090\/revisions"}],"predecessor-version":[{"id":1092,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1090\/revisions\/1092"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1091"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1090"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1090"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1090"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}