{"id":2431,"date":"2023-07-25T15:43:17","date_gmt":"2023-07-25T10:13:17","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2431"},"modified":"2023-07-25T15:43:19","modified_gmt":"2023-07-25T10:13:19","slug":"inorder-traversal-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/inorder-traversal-of-a-binary-tree\/","title":{"rendered":"Inorder Traversal Of A 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=\"#what-is-inorder-traversal\">What is Inorder Traversal?<\/a><\/li><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#inorder-traversal-with-recursion\">Inorder Traversal With Recursion<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><\/ul><li><a href=\"#inorder-traversal-iterative\">Inorder Traversal Iterative<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/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-how-do-you-find-the-inorder-on-a-traversal\">Q.1: How do you find the inorder on a traversal?<\/a><\/li><li><a href=\"#q2-is-inorder-traversal-on\">Q.2: Is inorder traversal o(n)?<\/a><\/li><li><a href=\"#q3-which-tree-traversal-is-most-efficient\">Q.3: Which tree traversal is most efficient?<\/a><\/li><li><a href=\"#q4-what-is-in-order-traversal-used-for\">Q.4: What is in-order traversal used for?<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"what-is-inorder-traversal\">What is Inorder Traversal?<\/h2>\n\n\n\n<p>It\u2019s a technique of traversing over all nodes of the tree. In inorder traversal of a binary tree, the whole left subtree then the current node, and after that, we traverse the right subtree<\/p>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>We have talked about binary trees in this section and not for the <a href=\"https:\/\/www.interviewbit.com\/blog\/n-ary-tree\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>n-ary tree<\/strong> <\/a>as we are not defined with the left or right child, so we can\u2019t follow a manner of traversing, so these techniques are most effective in the binary trees.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"842\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Binary Tree\"  class=\"wp-image-2473 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 842px) 100vw, 842px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree.jpg 842w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree-300x178.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree-768x456.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree-380x226.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree-550x327.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Binary-Tree-800x475.jpg 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"554\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Inorder Traversal Example 1\"  class=\"wp-image-2474 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 554px) 100vw, 554px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-1.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-1.jpg 554w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-1-300x271.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-1-380x343.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-1-550x496.jpg 550w\" ><\/figure><\/div>\n\n\n\n<p><strong>Inorder Traversal: 4 5 7 6 8<\/strong><\/p>\n\n\n\n<h2 id=\"inorder-traversal-with-recursion\">Inorder Traversal With Recursion<\/h2>\n\n\n\n<p>In inorder the flow of traversing will be left_subtree -&gt; current -&gt; right_subtree.<\/p>\n\n\n\n<ul><li>Base case: we have to check whether the node is present or not, i.e. not NULL.<\/li><li>Traverse left the child with a recursive call passing the current->left as root.<\/li><li>After returning from this call, the node would be leftmost so that we can store this first node of the inorder traversal.<\/li><li>Now we have the left child, and the root now makes a recursive call for the right subtree.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/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=\"\">void inorder(Tree* root) {\n   if(!root)return;\n   inorder(root->left,ans);\n   cout&lt;&lt;root->data&lt;&lt;endl;\n   inorder(root->right,ans);\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/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 InOrder(root):\n    if root:\n        # recursive call for left child\n        InOrder(root.left)\n        print(root.val),\n        # recursive call for the right child\n        InOrder(root.right)<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\"><span id=\"java-code-implementation-2\">Java Code Implementation<\/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=\"\">void InOrder(Tree root) {\n   if (root == null)\n     return;\n   InOrder(root.left);\n   System.out.print(root.key + \" \");\n   InOrder(root.right);\n}<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(N), Where N is no of nodes in the tree.<\/li><li><strong>Space complexity:<\/strong> O(1)<\/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=\"inorder-traversal-iterative\">Inorder Traversal Iterative<\/h2>\n\n\n\n<p>By this method, we iteratively traverse the trees. In this, we have to use the stack data structure.<\/p>\n\n\n\n<ul><li>Create a stack to store the values while traversing to the leftmost child.<\/li><li>Create a current node as root.<\/li><li>Traverse till the current node is not null or we have elements in our stack to process<\/li><li>As in order, we need the leftmost child first, so traverse to get the leftmost child in a nested loop.<\/li><li>Pop the top element from the stack and print it as it\u2019s the first node we needed and so on.<\/li><li>As our curr will be null after returning from the nested loop, make our current to the right of the top element as the left subtree, and the current node of the top element of the stack is processed, and now we have to traverse the right subtree.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/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 inOrder(struct Tree *root) {\n    stack&lt;Tree *> s;\n    Tree *curr = root;\n    while (curr != NULL || s.empty() == false)\n    {\n        while (curr !=  NULL)\n        {\n            s.push(curr);\n            curr = curr->left;\n        }\n        cout &lt;&lt; s.top()->data &lt;&lt; \" \";\n        curr = s.top()->right;\n        s.pop();\n    } \n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/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=\"\">void inorder() {\n  if (root == null)\n    return;\n  Stack &lt; Tree > s = new Stack &lt; Tree > ();\n  Tree curr = root;\n  while (curr != null || s.size() > 0) {\n    while (curr != null) {\n      curr = curr.left;\n    }\n    curr = s.pop();\n    System.out.print(curr.data + \" \");\n    curr = curr.right;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/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 inOrder(root):\n\n    current = root\n    stack = []\n    while True:\n        iterative\n        if current is not None:\n            stack.append(current)\n            current = current.left\n        elif stack:\n            current = stack.pop()\n            print(current.data, end=\" \")\n            current = current.right\n        else:\n            break<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(N), Where N is no of nodes in the tree.<\/li><li><strong>Space complexity:<\/strong> O(N).<\/li><\/ul>\n\n\n\n<p><strong>Inorder Traversal in Binary Search Tree: <\/strong>We can do inorder traversal in the binary search tree and find that the result will always be in the sorted order because of the property of the binary search tree that the left child is always smaller than the root and root will be smaller than the right child.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"554\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2475 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 554px) 100vw, 554px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example.jpg 554w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-300x271.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-380x343.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Inorder-Traversal-Example-550x496.jpg 550w\" ><\/figure><\/div>\n\n\n\n<p>Considering this BST we can see that the in-order traversal of this tree will be<\/p>\n\n\n\n<p><strong>In-order &#8211; 4 5 6 7 8<\/strong><\/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<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/inorder-traversal\/\" target=\"_blank\">Inorder Traversal Problem<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/inorder-traversal-of-cartesian-tree\/\" target=\"_blank\">Inorder Traversal Of Cartesian 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-how-do-you-find-the-inorder-on-a-traversal\"><span id=\"q-1-how-do-you-find-the-inorder-on-a-traversal\">Q.1: How do you find the inorder on a traversal?<\/span><\/h3>\n\n\n\n<p><strong>Ans<\/strong>: We can find the inorder using recursion or traversing the tree iteratively using a stack.<\/p>\n\n\n\n<h3 id=\"q2-is-inorder-traversal-on\"><span id=\"q-2-is-inorder-traversal-on\">Q.2: Is inorder traversal o(n)?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>Yes, but n here is the number of nodes in the tree.<\/p>\n\n\n\n<h3 id=\"q3-which-tree-traversal-is-most-efficient\"><span id=\"q-3-which-tree-traversal-is-most-efficient\">Q.3: Which tree traversal is most efficient?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> From Inorder, preorder, and postorder it depends according to your requirement as all the traversals are similar in terms of time complexities. Iterative is more efficient than recursive.<\/p>\n\n\n\n<h3 id=\"q4-what-is-in-order-traversal-used-for\"><span id=\"q-4-what-is-in-order-traversal-used-for\">Q.4: What is in-order traversal used for?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> It is used to traverse the tree in a given manner and use it according to our requirements and store it in other data structures or containers.<\/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\/level-order-traversal\/\" target=\"_blank\">Level Order Traversal of 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":"What is Inorder Traversal? It\u2019s a technique of traversing over all nodes of the tree. In inorder traversal&hellip;\n","protected":false},"author":5,"featured_media":2533,"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,406],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2431"}],"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=2431"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2431\/revisions"}],"predecessor-version":[{"id":21943,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2431\/revisions\/21943"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2533"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2431"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2431"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2431"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}