{"id":3322,"date":"2021-10-31T12:45:48","date_gmt":"2021-10-31T07:15:48","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3322"},"modified":"2022-07-08T15:25:07","modified_gmt":"2022-07-08T09:55:07","slug":"top-view-of-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/top-view-of-binary-tree\/","title":{"rendered":"Top 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=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">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=\"#faqs\">FAQs<\/a><\/li><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Binary Tree &#8211; A structure in which nodes are connected with each other in such a manner that every node can have a maximum of two children. <\/p>\n\n\n\n<p>Top view &#8211; set of nodes that are visible when viewing from the top. To print the top view of the binary tree we can print those nodes in any order&nbsp;<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-7211 pk-lazyload\"  width=\"414\"  height=\"512\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 414px) 100vw, 414px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-827x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-827x1024.png 827w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-242x300.png 242w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-768x951.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-1240x1536.png 1240w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-1654x2048.png 1654w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-380x471.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-550x681.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-800x991.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2-1160x1437.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2022\/02\/Asset-2-2.png 2836w\" ><\/figure><\/div>\n\n\n\n<p>Output of the above tree &#8211; 4 2 1 3&nbsp;<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3326 pk-lazyload\"  width=\"403\"  height=\"331\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 403px) 100vw, 403px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-12.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-12.png 656w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-12-300x246.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-12-380x312.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-12-550x451.png 550w\" ><\/figure><\/div>\n\n\n\n<p>Example &#8211; <\/p>\n\n\n\n<p><strong>Output:<\/strong> 4 6 7 11 9<br><strong>Explanation:<\/strong> As the nodes, 7,3,5 overlaps so we took only the top element as it\u2019s the only node that can be viewed from the top.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3327 pk-lazyload\"  width=\"340\"  height=\"279\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 340px) 100vw, 340px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-5.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-5.png 656w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-5-300x246.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-5-380x312.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-5-550x451.png 550w\" ><\/figure><\/div>\n\n\n\n<p>Example &#8211; <\/p>\n\n\n\n<p><strong>Output:<\/strong> 8 9 14 7<br><strong>Explanation:<\/strong> As the nodes 9,5,6 and 14,1 overlap so we took only the top elements from each overlapping set as it\u2019s the only node that can be viewed from the top.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<p>The approach is to use the preorder traversal of the tree to traverse the tree and check that we have visited the current vertical level and if visited then we can check for the smaller horizontal level node and store it. Else we can just update the vertical level as visited and store the node and horizontal level of the current node.<\/p>\n\n\n\n<ul><li>We have to create the map to check whether the horizontal level is visited or not as it will state the horizontal distance of the node from the root node. Where key will represent the horizontal distance and the value is the pair containing the value and level of each node.<\/li><li>We will traverse the tree using the preorder traversal.<\/li><li>Every time we check if the level of the current horizontal distance is less than the max level seen till now then we will update the value and the level for this horizontal distance.<\/li><li>We will pass level-1 for the left child and level+1 for the right child to get the vertical level.<\/li><li>Print the values present in the map.<\/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 Topview(Tree * head, int dis, int level, auto &amp; mp) {\n  if (head == nullptr) {\n    return;\n  }\n  if (mp.find(dis) == mp.end() || level &lt; mp[dis].second) {\n    mp[dis] = {\n      head -> key,\n      level\n    };\n  }\n  Topview(head -> left, dis - 1, level + 1, mp);\n  Topview(head -> right, dis + 1, level + 1, mp);\n}\nvoid Topview(Tree * head) {\n  mp &lt; int, pair &lt; int, int >> mp;\n  Topview(head, 0, 0, mp);\n  for (auto it: mp) {\n    cout &lt;&lt; it.second.first &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=\"\">class Pair &lt; U, V > {\n  public final U first;\n  public final V second;\n  private Pair(U first, V second) {\n    this.first = first;\n    this.second = second;\n  }\n  public static &lt; U,\n  V > Pair &lt; U,\n  V > of (U a, V b) {\n    return new Pair &lt; > (a, b);\n  }\n}\n\nclass Main {\n  public static void topView(Tree head, int dis, int level,\n    Map &lt; Integer, Pair &lt; Integer, Integer >> map) {\n    if (head == null) {\n      return;\n    }\n    if (!map.containsKey(dis) || level &lt; map.get(dis).second) {\n      map.put(dis, Pair.of(head.key, level));\n    }\n    topView(head.left, dis - 1, level + 1, map);\n    topView(head.right, dis + 1, level + 1, map);\n  }\n  public static void topView(Tree head) {\n    Map &lt; Integer, Pair &lt; Integer, Integer >> map = new TreeMap &lt; > ();\n    topView(head, 0, 0, map);\n    for (Pair &lt; Integer, Integer > it: map.values()) {\n      System.out.print(it.first + \" \");\n    }\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 topView(head, dis, level, dict):\n\n    if head is None:\n        return\n\n    if dis not in dict or level &lt; dict[dis][1]:\n        dict[dis] = (head.key, level)\n    topView(head.left, dis - 1, level + 1, dict)\n    topView(head.right, dis + 1, level + 1, dict)\n\ndef printTopView(head):\n    dict = {}\n\n    topView(head, 0, 0, dict)\n    for key in sorted(dict.keys()):\n        print(dict.get(key)[0], end=' ')<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(N), Where N is the size of the array.<br><strong>Space complexity:<\/strong> O(1)<\/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<p><strong>Practice Question<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/vertical-order-traversal-of-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Vertical Order Traversal<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>How do you find the top view of a tree?<\/strong><br>We have to find the nodes which are visible from the top so we can find it recursively storing<br>The horizontal distance of every node from the root node.<\/p>\n\n\n\n<p><strong>What is a treetop view?<\/strong><br>It\u2019s the set of nodes visible when a tree is viewed from the top.<\/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 href=\"https:\/\/www.interviewbit.com\/blog\/level-order-traversal\/\" target=\"_blank\" rel=\"noreferrer noopener\">Level Order Traversal 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\/bottom-view-of-binary-tree\/\" target=\"_blank\">Bottom View 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":"Problem Statement Binary Tree &#8211; A structure in which nodes are connected with each other in such a&hellip;\n","protected":false},"author":5,"featured_media":3329,"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":[395],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3322"}],"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\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3322"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3322\/revisions"}],"predecessor-version":[{"id":10286,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3322\/revisions\/10286"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3329"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3322"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3322"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3322"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}