{"id":27668,"date":"2018-04-09T20:21:07","date_gmt":"2018-04-09T14:51:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27668"},"modified":"2018-09-14T18:31:46","modified_gmt":"2018-09-14T13:01:46","slug":"java-program-inorder-tree-traversal-without-recursion-without-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-inorder-tree-traversal-without-recursion-without-stack\/","title":{"rendered":"Program &#8211; Inorder Tree Traversal without recursion and without stack!"},"content":{"rendered":"<p>Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on <a href=\"http:\/\/en.wikipedia.org\/wiki\/Threaded_binary_tree\" target=\"_blank\" rel=\"noopener\">Threaded Binary Tree<\/a>. <span id=\"more-6358\"><\/span>In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.<\/p>\n<pre>1. Initialize current as root \r\n2. While current is not NULL\r\n   If current does not have left child\r\n      a) Print current\u2019s data\r\n      b) Go to the right, i.e., current = current-&gt;right\r\n   Else\r\n      a) Make current as right child of the rightmost \r\n         node in current's left subtree\r\n      b) Go to this left child, i.e., current = current-&gt;left\r\n<\/pre>\n<p>Although the tree is modified through the traversal, it is reverted back to its original shape after the completion. Unlike <a href=\"http:\/\/www.geeksforgeeks.org\/?p=5592\" target=\"_blank\" rel=\"noopener\">Stack based traversal<\/a>, no extra space is required for this traversal.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ Java program to print inorder traversal without recursion and stack<br\/>  <br\/>\/* A binary tree tNode has data, pointer to left child<br\/>   and a pointer to right child *\/<br\/>class tNode <br\/>{<br\/>    int data;<br\/>    tNode left, right;<br\/>      <br\/>    tNode(int item) <br\/>    {<br\/>        data = item;<br\/>        left = right = null;<br\/>    }<br\/>}<br\/>  <br\/>class BinaryTree <br\/>{<br\/>    tNode root;<br\/>  <br\/>    \/* Function to traverse binary tree without recursion and <br\/>       without stack *\/<br\/>    void MorrisTraversal(tNode root) {<br\/>        tNode current, pre;<br\/>          <br\/>        if (root == null)<br\/>            return;<br\/>          <br\/>        current = root;<br\/>        while (current != null) <br\/>        {<br\/>            if (current.left == null) <br\/>            {<br\/>                System.out.print(current.data + &quot; &quot;);<br\/>                current = current.right;<br\/>            }<br\/>            else<br\/>            {<br\/>                \/* Find the inorder predecessor of current *\/<br\/>                pre = current.left;<br\/>                while (pre.right != null &amp;&amp; pre.right != current) <br\/>                    pre = pre.right;<br\/>                 <br\/>                \/* Make current as right child of its inorder predecessor *\/<br\/>                if (pre.right == null) <br\/>                {<br\/>                    pre.right = current;<br\/>                    current = current.left;<br\/>                } <br\/>  <br\/>                 \/* Revert the changes made in if part to restore the <br\/>                    original tree i.e.,fix the right child of predecssor*\/<br\/>                 else<br\/>                 {<br\/>                    pre.right = null;<br\/>                    System.out.print(current.data + &quot; &quot;);<br\/>                    current = current.right;<br\/>                }   \/* End of if condition pre-&gt;right == NULL *\/<br\/>                  <br\/>            } \/* End of if condition current-&gt;left == NULL*\/<br\/>              <br\/>        } \/* End of while *\/<br\/>          <br\/>    }<br\/>      <br\/>    public static void main(String args[]) <br\/>    {<br\/>        \/* Constructed binary tree is<br\/>               1<br\/>             \/   \\<br\/>            2      3<br\/>          \/  \\<br\/>        4     5<br\/>        *\/<br\/>        BinaryTree tree = new BinaryTree();<br\/>        tree.root = new tNode(1);<br\/>        tree.root.left = new tNode(2);<br\/>        tree.root.right = new tNode(3);<br\/>        tree.root.left.left = new tNode(4);<br\/>        tree.root.left.right = new tNode(5);<br\/>          <br\/>        tree.MorrisTraversal(tree.root);<br\/>    }<br\/>}<br\/>  <br\/>\/\/ This code has been contributed by Mayank Jaiswal(mayank_24)<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>4 2 5 1 3<\/pre>\n","protected":false},"excerpt":{"rendered":"<p> Inorder Tree Traversal without recursion and without stack! &#8211; Using Morris Traversal, we can traverse the tree without using stack and recursion.<\/p>\n","protected":false},"author":1,"featured_media":31268,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80125,80140],"tags":[81943,81802,81944,81803,81805,81800,81801,81804],"class_list":["post-27668","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binary-tree","category-binay-tree","tag-binary-tree-traversal-without-recursion","tag-inorder-preorder-postorder-traversal-without-recursion-in-c","tag-inorder-traversal-of-threaded-binary-tree","tag-inorder-traversal-with-recursion","tag-inorder-traversal-with-recursion-in-c","tag-inorder-traversal-without-recursion-and-stack","tag-postorder-traversal-without-recursion","tag-postorder-traversal-without-recursion-and-stack"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27668","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27668"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27668\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31268"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}