{"id":3884,"date":"2021-11-18T14:54:47","date_gmt":"2021-11-18T09:24:47","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3884"},"modified":"2022-07-08T15:28:55","modified_gmt":"2022-07-08T09:58:55","slug":"left-view-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/left-view-of-a-binary-tree\/","title":{"rendered":"Left View of a Binary Tree"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><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=\"#method-1-using-recursion\">Method-1 (Using Recursion)<\/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=\"#method-2-using-queue\">Method-2 (Using Queue):<\/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&nbsp;<\/a><\/li><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p><strong>What is Print Left View of a Binary Tree Problem?<\/strong><\/p>\n\n\n\n<p>Given a binary tree, the left view of a binary tree is the set of all those nodes visible from the left side of the binary tree. In other words it is the set of first node of every level.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"596\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Binary Tree\"  class=\"wp-image-4001 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 596px) 100vw, 596px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/binary-tree.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/binary-tree.png 596w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/binary-tree-300x252.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/binary-tree-380x319.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/binary-tree-550x461.png 550w\" ><\/figure>\n\n\n\n<h2 id=\"method-1-using-recursion\">Method-1 (Using Recursion)<\/h2>\n\n\n\n<p>The left view contains all nodes that are first in every level. A simple solution is to do level order traversal (traversing the tree level by level) and print the first node in every level.<\/p>\n\n\n\n<p>This problem can be solved with the help of using simple recursion. Basically the idea is to print all the first nodes in every level. For this, we just keep visiting the left subtree before the right subtree with the height as a parameter of their respective nodes. The idea is to keep track of the maximum level that is already visited, if the current level is greater then the maximum level then print that node because that node is the first in its level.<\/p>\n\n\n\n<p><strong>Below is the implementation of the above idea-<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/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=\"\">\/\/ C++ program to print left view of Binary Tree\n#include &amp;lt;bits\/stdc++.h&amp;gt;\nusing namespace std;\n\nstruct Node\n{\n    int val;\n    struct Node *left, *right;\n};\n\n\/\/ A function to\n\/\/ create a new Binary Tree Node\nstruct Node *newNode(int data)\n{\n    struct Node *temp = new Node();\n    temp-&amp;gt;val = data;\n    temp-&amp;gt;left = NULL;\n    temp-&amp;gt;right = NULL;\n    return temp;\n}\n\n\/\/ A Recursive function to print the nodes\n\/\/ of left view of a binary tree.\nvoid leftView(struct Node *root, int level, int *max_level)\n{\n    \/\/ Base Case\n    if (root == NULL) return;\n\n    \/\/ If this is the left most Node of its level\n    if (*max_level &amp;lt; level)\n    {\n        cout &amp;lt;&amp;lt; root-&amp;gt;val &amp;lt;&amp;lt; \" \";\n*max_level = level;\n    }\n\n    \/\/ Recur call for left subtree first,\n    \/\/ then right subtree\n    leftView(root-&amp;gt;left, level + 1, max_level);\n    leftView(root-&amp;gt;right, level + 1, max_level);\n    \n}\n\n\/\/ Driver Code\nint main()\n{\n    Node* root = newNode(1);\n    root-&amp;gt;left = newNode(2);\n    root-&amp;gt;right = newNode(3);\n    root-&amp;gt;left-&amp;gt;left = newNode(4);\n    root-&amp;gt;left-&amp;gt;right = newNode(5);\n    root-&amp;gt;right-&amp;gt;right = newNode(6);\n    root-&amp;gt;right-&amp;gt;right-&amp;gt;right = newNode(7);\n    int max_level = 0;\n    leftView(root, 1, &amp;amp;max_level);\n\n    return 0;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/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=\"\">\/\/ A Recursive function to print the nodes\n\/\/ of left view of a binary tree.\n\nvoid leftViewUtil(Node node, int level)\n    {\n        \/\/ Base Case\n        if (node == null)\n            return;\n\n        \/\/ If this is the left most Node of its level\n        if (max_level &amp;lt; level) {\n            System.out.print(\" \" + node.val);\n            max_level = level;\n        }\n\n        \/\/ Recur call for left subtree first,\n          \/\/ then right subtree\n        leftViewUtil(node.left, level + 1);\n        leftViewUtil(node.right, level + 1);\n    }<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/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 leftView(root, level, max_level):\n     \n    # Base Case\n    if root is None:\n        return\n \n    # If this is the first node of its level\n    if (max_level[0] &amp;lt; level):\n        print \"% d\\t\" %(root.val),\n        max_level[0] = level\n \n    # Recur for left and right subtree\n    leftViewUtil(root.left, level + 1, max_level)\n    leftViewUtil(root.right, level + 1, max_level)<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>Just a dfs traversal of a binary tree, Time Complexity of the above approach is O(n).<\/p>\n\n\n\n<p><strong>Auxiliary Space: <\/strong>O(n), due to the stack space during recursive call.&nbsp;<\/p>\n\n\n\n<h2 id=\"method-2-using-queue\">Method-2 (Using Queue):<\/h2>\n\n\n\n<p>In this method,a solution based on level order traversal is discussed. Our main aim to solve this problem is to find the left most node of every level. So we will solve this by using a simple level order traversal and print the leftmost node at every level. For this, we\u2019ll use queue to store all the nodes in the current level,&nbsp;<\/p>\n\n\n\n<ul><li>we\u2019ll print out the first node and,<\/li><li>loop through the nodes in the queue and,<\/li><li>&nbsp;push all the child nodes and pop the parent out, basically this will give us the nodes present in the next level and,<\/li><li>&nbsp;repeat the steps until the queue is empty.&nbsp;<\/li><\/ul>\n\n\n\n<p><strong>Code for above implementation,&nbsp;<\/strong><\/p>\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=\"\">\/\/ function to print left view of\n\/\/ binary tree\nvoid LeftView(Node* root)\n{\n    if (root==NULL)\n        return;\n\n    queue&amp;lt;Node*&amp;gt; q;\n    q.push(root);\n\n    while (!q.empty())\n    {    \n        \/\/ number of nodes at current level\n        int n = q.size();\n                 \/\/ function to print left view of\n                 \/\/ binary tree\n                 cout&amp;lt;&amp;lt;q.front()-&amp;gt;data&amp;lt;&amp;lt;\" \";\n        \n        \/\/ Traverse all nodes of current level\n        for(int i = 0; i &amp;lt; n; i++)\n        {\n            Node* temp = q.front();\n            q.pop();\n            \n            \/\/ Add left node to queue\n            if (temp-&amp;gt;left != NULL)\n                q.push(temp-&amp;gt;left);\n\n            \/\/ Add right node to queue\n            if (temp-&amp;gt;right != NULL)\n                q.push(temp-&amp;gt;right);\n        }\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=\"\">private static void LeftView(Node root)\n    {\n        if (root == null)\n            return;\n \n        Queue&amp;lt;Node&amp;gt; q = new LinkedList&amp;lt;&amp;gt;();\n        q.add(root);\n \n        while (!q.isEmpty()) {\n            \/\/ number of nodes at current level\n            int n = q.size();\n            \n            \/\/ Print the left most element at\n            \/\/ the level\n            System.out.print(q.poll().data + \" \");\n            \n            \/\/ Traverse all nodes of current level\n            for (int i = 0; i &amp;lt; n; i++) {\n                Node temp = q.poll();\n \n                \/\/ Add left node to queue\n                if (temp.left != null)\n                    q.add(temp.left);\n \n                \/\/ Add right node to queue\n                if (temp.right != null)\n                    q.add(temp.right);\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 printRightView(root):\n \n    if (not root):\n        return\n \n    q = []\n    q.append(root)\n \n    while (len(q)):\n \n        # number of nodes at current level\n        n = len(q)\n \n        # Print the left most element\n        # at the level\n        print(q[0].data, end=\" \")\n        \n        \n        # Traverse all nodes of current level\n        for i in range(0, n):\n            temp = q[0]\n            q.pop(0)\n \n            # Add left node to queue\n            if (temp.left != None):\n                q.append(temp.left)\n \n            # Add right node to queue\n            if (temp.right != None):\n                q.append(temp.right)<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(n), where n is the number of nodes in the binary tree.<\/p>\n\n\n\n<p id=\"-practice-problem-\"><strong>Practice Problem<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/right-view-of-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Right view of Binary tree<\/a><\/p>\n\n\n\n<h2 id=\"faqs-\"><span id=\"faqs\">FAQs&nbsp;<\/span><\/h2>\n\n\n\n<ul><li><strong>What is level order traversal ?<\/strong><\/li><\/ul>\n\n\n\n<p>Level order traversal is travelling tree level by level.<\/p>\n\n\n\n<ul><li><strong>Can we find the left view of a binary tree using preorder traversal?<\/strong><\/li><\/ul>\n\n\n\n<p>Yes, we just have to keep a track of current height for a node and if we visit a height for the first time we\u2019ll print that element out.<\/p>\n\n\n\n<ul><li><strong>How to print the right view of a binary tree?<\/strong><\/li><\/ul>\n\n\n\n<p>Right view is basically the right most element in a level thus we can use the same approach as mentioned above but instead of the first node we\u2019ll print the last node.<\/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\/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\/level-order-traversal\/\" target=\"_blank\">Level Order Traversal of Binary Tree<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"What is Print Left View of a Binary Tree Problem? Given a binary tree, the left view of&hellip;\n","protected":false},"author":5,"featured_media":4000,"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,577],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3884"}],"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=3884"}],"version-history":[{"count":7,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3884\/revisions"}],"predecessor-version":[{"id":10294,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3884\/revisions\/10294"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4000"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3884"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3884"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3884"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}