{"id":1087,"date":"2025-09-02T12:15:56","date_gmt":"2025-09-02T06:45:56","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1087"},"modified":"2025-09-02T12:15:57","modified_gmt":"2025-09-02T06:45:57","slug":"top-view-of-binary-tree","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/top-view-of-binary-tree\/","title":{"rendered":"Top View of Binary Tree | BFS with Horizontal Distance Mapping"},"content":{"rendered":"\n<p>The <strong>Top View of Binary Tree<\/strong> problem asks us to return the set of nodes visible when looking at the binary tree from <strong>above<\/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>first node encountered during level-order traversal (BFS)<\/strong> is part of the top 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\/top-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      1\n     \/ \\\n    2   3\n     \\\n      4\n       \\\n        5\n         \\\n          6\n\nOutput: [2, 1, 3, 6]\nExplanation: From the top, nodes 2, 1, 3, and 6 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\">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 style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">5<\/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\">6<\/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\">2<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">6<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Explanation<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">From the top, nodes 2, 1, 3, and 6 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       10\n      \/  \\\n     20   30\n    \/  \\\n   40  60\n\nOutput: [40, 20, 10, 30]\" 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\">10<\/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\">20   30<\/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\">40  60<\/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\">40<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">20<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">10<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">30<\/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 to track the <strong>horizontal distance (HD)<\/strong> of each node during traversal.<\/p>\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>Use BFS (level-order traversal) to ensure that the <strong>first node<\/strong> at each HD is captured.<\/li>\n\n\n\n<li>Maintain a dictionary <code>hd_map<\/code> where:\n<ul class=\"wp-block-list\">\n<li><strong>Key = HD<\/strong><\/li>\n\n\n\n<li><strong>Value = Node data<\/strong><\/li>\n\n\n\n<li>Only store the <strong>first occurrence<\/strong> of each HD.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Traverse the entire tree, updating left and right children with HD &#8211; 1 and HD + 1.<\/li>\n\n\n\n<li>Sort keys of <code>hd_map<\/code> and return values in order.<\/li>\n<\/ol>\n\n\n\n<p>This guarantees that we collect the correct top view.<\/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=\"# Tree Node\n# class Node:\n#     def __init__(self, val):\n#         self.right = None\n#         self.data = val\n#         self.left = None\n\nfrom collections import deque\n\nclass Solution:\n    def topView(self, root):\n        if not root:\n            return []\n        \n        # dictionary to store first 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            # store the first node we encounter at this HD\n            if hd not in hd_map:\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: #6A9955\"># Tree Node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\"># class Node:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#     def __init__(self, val):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.right = None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.data = val<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.left = None<\/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\">topView<\/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 first 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\"># store the first node we encounter at this HD<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> hd <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> hd_map:<\/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 traverse the tree 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>Captures only the first node at each HD.<\/li>\n\n\n\n<li>Ensures top-most node is chosen.<\/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 print nodes from <strong>leftmost to rightmost<\/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\">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=\"      1\n     \/ \\\n    2   3\n     \\\n      4\n       \\\n        5\n         \\\n          6\" 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\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     \/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">3<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">5<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">         \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">          <\/span><span style=\"color: #B5CEA8\">6<\/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>Start \u2192 (1, 0) \u2192 store <code>hd_map[0] = 1<\/code>.<\/li>\n\n\n\n<li>Left \u2192 (2, -1) \u2192 store <code>hd_map[-1] = 2<\/code>.<\/li>\n\n\n\n<li>Right \u2192 (3, +1) \u2192 store <code>hd_map[1] = 3<\/code>.<\/li>\n\n\n\n<li>Next \u2192 (4, 0) \u2192 already exists, ignore.<\/li>\n\n\n\n<li>Next \u2192 (5, 1) \u2192 already exists, ignore.<\/li>\n\n\n\n<li>Next \u2192 (6, 2) \u2192 store <code>hd_map[2] = 6<\/code>.<\/li>\n<\/ol>\n\n\n\n<p>Final <code>hd_map = {-1:2, 0:1, 1:3, 2:6}<\/code><\/p>\n\n\n\n<p>Sorted output = <code>[2, 1, 3, 6]<\/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 of <code>hd_map<\/code> \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 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>Top View of Binary Tree<\/strong> problem is solved efficiently using <strong>BFS and horizontal distance mapping<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Each node is assigned an HD.<\/li>\n\n\n\n<li>The first node encountered at each HD is chosen.<\/li>\n\n\n\n<li>Sorting ensures correct left-to-right order.<\/li>\n<\/ul>\n\n\n\n<p>This method runs in <strong>O(N log K)<\/strong> time and <strong>O(N)<\/strong> space, making it optimal for large binary trees.<\/p>\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\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Top View of Binary Tree problem asks us to return the set of nodes visible when looking at the binary tree from above. 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 to<\/p>\n","protected":false},"author":1,"featured_media":1089,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[14,19],"class_list":{"0":"post-1087","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\/top-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\/1087","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=1087"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1087\/revisions"}],"predecessor-version":[{"id":1088,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1087\/revisions\/1088"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1089"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1087"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1087"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1087"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}