{"id":27669,"date":"2018-04-09T20:21:05","date_gmt":"2018-04-09T14:51:05","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27669"},"modified":"2018-09-14T18:40:23","modified_gmt":"2018-09-14T13:10:23","slug":"python-program-inorder-tree-traversal-without-recursion-without-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-tree-traversal-without-recursion-without-stack\/","title":{"rendered":"Python 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\">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->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->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\">Stack based traversal<\/a>, no extra space is required for this traversal.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20do%20inorder%20traversal%20without%20recursion%20and%20%0A%23%20without%20stack%20Morris%20inOrder%20Traversal%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20Iterative%20function%20for%20inorder%20tree%20traversal%0Adef%20MorrisTraversal(root)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Set%20current%20to%20root%20of%20binary%20tree%0A%20%20%20%20current%20%3D%20root%20%0A%20%20%20%20%20%0A%20%20%20%20while(current%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20current.left%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20current.data%20%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.right%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23Find%20the%20inorder%20predecessor%20of%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20pre%20%3D%20current.left%0A%20%20%20%20%20%20%20%20%20%20%20%20while(pre.right%20is%20not%20None%20and%20pre.right%20!%3D%20current)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre%20%3D%20pre.right%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Make%20current%20as%20right%20child%20of%20its%20inorder%20predecessor%0A%20%20%20%20%20%20%20%20%20%20%20%20if(pre.right%20is%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre.right%20%3D%20current%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.left%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Revert%20the%20changes%20made%20in%20if%20part%20to%20restore%20the%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20original%20tree%20i.e.%2C%20fix%20the%20right%20child%20of%20predecssor%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre.right%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20current.data%20%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.right%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%23%20Driver%20program%20to%20test%20above%20function%0A%22%22%22%20%0AConstructed%20binary%20tree%20is%0A%20%20%20%20%20%20%20%20%20%20%20%201%0A%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%5C%0A%20%20%20%20%20%20%20%202%20%20%20%20%20%203%0A%20%20%20%20%20%20%2F%20%20%5C%0A%20%20%20%204%20%20%20%20%205%0A%22%22%22%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0A%20%0AMorrisTraversal(root)%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Naveen%20Aili\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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":31269,"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-27669","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\/27669","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=27669"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27669\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31269"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27669"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}