{"id":2275,"date":"2023-06-12T13:59:39","date_gmt":"2023-06-12T08:29:39","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2275"},"modified":"2023-06-12T14:35:05","modified_gmt":"2023-06-12T09:05:05","slug":"level-order-traversal","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/level-order-traversal\/","title":{"rendered":"Level Order Traversal of 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=\"text_open\">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><ul class=\"gutentoc-toc__list\"><li><a href=\"#example-1\">Example 1:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#input\">Input:<\/a><\/li><li><a href=\"#output\">Output:<\/a><\/li><\/ul><li><a href=\"#example-2\">Example 2:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#input\">Input:<\/a><\/li><li><a href=\"#output\">Output:<\/a><\/li><\/ul><\/ul><li><a href=\"#1-recursive-approach\">1. Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation-of-recursive-approach\">Implementation of Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#1-level-order-traversal-in-c\">1. Level Order Traversal in C<\/a><\/li><li><a href=\"#2-level-order-traversal-in-c\">2. Level Order Traversal in C++<\/a><\/li><li><a href=\"#3-level-order-traversal-in-java\">3. Level Order Traversal in Java<\/a><\/li><li><a href=\"#4-level-order-traversal-in-python\">4. Level Order Traversal in Python<\/a><\/li><\/ul><\/ul><li><a href=\"#2-level-order-traversal-using-queue\">2. Level Order Traversal Using Queue<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation-of-the-above-approach\">Implementation of the above Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#1-c-implementation\">1. C++ Implementation<\/a><\/li><li><a href=\"#2-java-implementation\">2. Java Implementation<\/a><\/li><li><a href=\"#3-python-implementation\">3. Python Implementation<\/a><\/li><\/ul><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-level-order-traversal-of-a-tree\">Q.1: What is the level order traversal of a tree?<\/a><\/li><li><a href=\"#q2-how-do-you-do-level-order-traversal\">Q.2: How do you do level order traversal?<\/a><\/li><li><a href=\"#q3-is-level-order-traversal-the-same-as-bfs\">Q.3: Is Level order traversal the same as BFS?<\/a><\/li><li><a href=\"#q4-when-should-i-use-level-order-traversal\">Q.4: When should I use level order traversal?<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc.<\/p>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a binary tree, the task is to print the level order traversal line by line of the tree<\/p>\n\n\n\n<h3 id=\"example-1\">Example 1:<\/h3>\n\n\n\n<h4 id=\"input\"><span id=\"input-2\">Input:<\/span><\/h4>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"binary tree\"  class=\"wp-image-2282 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2-300x146.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2-768x375.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2-380x186.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2-550x269.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-2-800x391.jpg 800w\" ><\/figure>\n\n\n\n<h4 id=\"output\"><span id=\"output-2\">Output:<\/span><\/h4>\n\n\n\n<p id=\"level1-nodes-1-level-2-nodes-23-level-3-nodes-45-level-4-nodes-67\">Level1 nodes: 1<br>Level 2 nodes: 2,3<br>Level 3 nodes: 4,5<br>Level 4 nodes 6,7<\/p>\n\n\n\n<h3 id=\"example-2\">Example 2:<\/h3>\n\n\n\n<h4 id=\"input\">Input:<\/h4>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"level order traversal\"  class=\"wp-image-2279 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2-300x146.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2-768x375.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2-380x186.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2-550x269.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-2-800x391.jpg 800w\" ><\/figure><\/div>\n\n\n\n<h4 id=\"output\">Output:<\/h4>\n\n\n\n<p>Level1 nodes: 50<br>Level 2 nodes: 35,57<br>Level 3 nodes: 30,40,52,58<br>Level 4 nodes: 11<\/p>\n\n\n\n<p>There are two approaches to solving this problem:<\/p>\n\n\n\n<h2 id=\"1-recursive-approach\">1. Recursive Approach<\/h2>\n\n\n\n<p>There are basically two functions in this approach. One of them is used to print all nodes at a particular level (CurrentLevel), and another is used to print the level order traversal of the tree (Levelorder).<\/p>\n\n\n\n<ul><li>In the CurrentLevel function, we find the height of the tree and call the LevelOrder function for every level between 1 to height.<\/li><li>In the LevelOrder function, we pass two parameters level and root. we follow the below steps:<ul><li>First, check if the root is null then return.<\/li><li>Check if the level is equal to 1 then print the current root value.<\/li><li>Now, call recursively call both the children of the current root with decrementing the value of level by 1.<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"implementation-of-recursive-approach\">Implementation of Recursive Approach<\/h3>\n\n\n\n<h4 id=\"1-level-order-traversal-in-c\">1. Level Order Traversal in C<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/8cb6db9227f2af8839c8 title='Interviewbit Ide snippet\/8cb6db9227f2af8839c8' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"2-level-order-traversal-in-c\">2. Level Order Traversal in C++<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/afca3703481f2f115f2c title='Interviewbit Ide snippet\/afca3703481f2f115f2c' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"3-level-order-traversal-in-java\">3. Level Order Traversal in Java<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/bc361c2987d378b22b62 title='Interviewbit Ide snippet\/bc361c2987d378b22b62' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"4-level-order-traversal-in-python\">4. Level Order Traversal in Python<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/ca53d264d9ebb0641fdf title='Interviewbit Ide snippet\/ca53d264d9ebb0641fdf' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> For a skewed tree, time complexity will be O(n^2).<\/li><li><strong>Space complexity:<\/strong> For a skewed tree space complexity will be O(n) and for a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).<\/li><\/ul>\n\n\n\n<h2 id=\"2-level-order-traversal-using-queue\">2. Level Order Traversal Using Queue<\/h2>\n\n\n\n<p>Firstly we insert the root into the queue and iterate over the queue until the queue is empty.<br>In every iteration, we will pop from the top of the queue and print the value at the top of the queue.<br>Then, add its left and right nodes to the end of the queue.<\/p>\n\n\n\n<h3 id=\"implementation-of-the-above-approach\">Implementation of the above Approach<\/h3>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"843\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run\"  class=\"wp-image-2281 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2-300x247.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2-768x632.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2-380x313.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2-550x453.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-2-800x659.jpg 800w\" ><\/figure>\n\n\n\n<h4 id=\"1-c-implementation\">1. C++ Implementation<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/fd51a130b3d62d3509ed title='Interviewbit Ide snippet\/fd51a130b3d62d3509ed' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"2-java-implementation\">2. Java Implementation<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/74af0fbec90ffd0e5ad0 title='Interviewbit Ide snippet\/74af0fbec90ffd0e5ad0' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"3-python-implementation\">3. Python Implementation<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/3080ab73a2366daa5b93 title='Interviewbit Ide snippet\/3080ab73a2366daa5b93' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N) where n is the number of nodes in the binary tree.<\/li><li><strong>Space Complexity:<\/strong> O(N) where n is the number of nodes in the binary tree.<\/li><\/ul>\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<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/zigzag-level-order-traversal-bt\/\" target=\"_blank\">Zigzag Level Order Traversal BT<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/right-view-of-binary-tree\/\" target=\"_blank\">Right View Of Binary Tree<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/cousins-in-binary-tree\/\" target=\"_blank\">Cousins In Binary Tree<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/problems\/identical-binary-trees\/\" target=\"_blank\" rel=\"noreferrer noopener\">Identical Binary Trees<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/problems\/2sum-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">2-Sum Binary Tree<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/problems\/min-depth-of-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Min Depth of Binary Tree<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/problems\/last-node-in-a-complete-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Last Node in a Complete Binary Tree<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/problems\/max-sum-path-in-binary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\">Max Sum Path in Binary Tree<\/a><\/li><\/ul>\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<h3 id=\"q1-what-is-the-level-order-traversal-of-a-tree\"><span id=\"q-1-what-is-the-level-order-traversal-of-a-tree\">Q.1: What is the level order traversal of a tree?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc.<\/p>\n\n\n\n<h3 id=\"q2-how-do-you-do-level-order-traversal\"><span id=\"q-2-how-do-you-do-level-order-traversal\">Q.2: How do you do level order traversal?<\/span><\/h3>\n\n\n\n<p><strong>Ans<\/strong>: Level order traversal can be done by using a queue and traversing nodes by depth.<\/p>\n\n\n\n<h3 id=\"q3-is-level-order-traversal-the-same-as-bfs\"><span id=\"q-3-is-level-order-traversal-the-same-as-bfs\">Q.3: Is Level order traversal the same as BFS?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, both the algorithms are the same as both traverse the nodes by depth.<\/p>\n\n\n\n<h3 id=\"q4-when-should-i-use-level-order-traversal\"><span id=\"q-4-when-should-i-use-level-order-traversal\">Q.4: When should I use level order traversal?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Level order traversal is actually a Breadth-First Search, which can be used to solve many problems in graph theory, for example: Finding all nodes within one connected component.<\/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\/left-view-of-a-binary-tree\/\" target=\"_blank\">Left View of a Binary Tree<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first&hellip;\n","protected":false},"author":5,"featured_media":2278,"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":[394],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2275"}],"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=2275"}],"version-history":[{"count":16,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2275\/revisions"}],"predecessor-version":[{"id":20001,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2275\/revisions\/20001"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2278"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}