{"id":27659,"date":"2018-04-09T20:17:37","date_gmt":"2018-04-09T14:47:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27659"},"modified":"2018-09-14T19:30:16","modified_gmt":"2018-09-14T14:00:16","slug":"27659-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/27659-2\/","title":{"rendered":"C Program – Inorder Tree Traversal without recursion and without stack!"},"content":{"rendered":"

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree<\/a>. <\/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

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
Although the tree is modified through the traversal, it is reverted back to its original shape after the completion. Unlike Stack based traversal<\/a>, no extra space is required for this traversal.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20binary%20tree%20tNode%20has%20data%2C%20pointer%20to%20left%20child%0A%20%20%20and%20a%20pointer%20to%20right%20child%20*%2F%0Astruct%20tNode%0A%7B%0A%20%20%20int%20data%3B%0A%20%20%20struct%20tNode*%20left%3B%0A%20%20%20struct%20tNode*%20right%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20traverse%20binary%20tree%20without%20recursion%20and%20%0A%20%20%20without%20stack%20*%2F%0Avoid%20MorrisTraversal(struct%20tNode%20*root)%0A%7B%0A%20%20struct%20tNode%20*current%2C*pre%3B%0A%20%0A%20%20if(root%20%3D%3D%20NULL)%0A%20%20%20%20%20return%3B%20%0A%20%0A%20%20current%20%3D%20root%3B%0A%20%20while(current%20!%3D%20NULL)%0A%20%20%7B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20if(current-%3Eleft%20%3D%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20printf(%22%25d%20%22%2C%20current-%3Edata)%3B%0A%20%20%20%20%20%20current%20%3D%20current-%3Eright%3B%20%20%20%20%20%20%0A%20%20%20%20%7D%20%20%20%20%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2F*%20Find%20the%20inorder%20predecessor%20of%20current%20*%2F%0A%20%20%20%20%20%20pre%20%3D%20current-%3Eleft%3B%0A%20%20%20%20%20%20while(pre-%3Eright%20!%3D%20NULL%20%26%26%20pre-%3Eright%20!%3D%20current)%0A%20%20%20%20%20%20%20%20pre%20%3D%20pre-%3Eright%3B%0A%20%0A%20%20%20%20%20%20%2F*%20Make%20current%20as%20right%20child%20of%20its%20inorder%20predecessor%20*%2F%0A%20%20%20%20%20%20if(pre-%3Eright%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20pre-%3Eright%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Eleft%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F*%20Revert%20the%20changes%20made%20in%20if%20part%20to%20restore%20the%20original%20%0A%20%20%20%20%20%20%20%20tree%20i.e.%2C%20fix%20the%20right%20child%20of%20predecssor%20*%2F%20%20%20%0A%20%20%20%20%20%20else%20%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20pre-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2Ccurrent-%3Edata)%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Eright%3B%20%20%20%20%20%20%0A%20%20%20%20%20%20%7D%20%2F*%20End%20of%20if%20condition%20pre-%3Eright%20%3D%3D%20NULL%20*%2F%0A%20%20%20%20%7D%20%2F*%20End%20of%20if%20condition%20current-%3Eleft%20%3D%3D%20NULL*%2F%0A%20%20%7D%20%2F*%20End%20of%20while%20*%2F%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Helper%20function%20that%20allocates%20a%20new%20tNode%20with%20the%0A%20%20%20given%20data%20and%20NULL%20left%20and%20right%20pointers.%20*%2F%0Astruct%20tNode*%20newtNode(int%20data)%0A%7B%0A%20%20struct%20tNode*%20tNode%20%3D%20(struct%20tNode*)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20malloc(sizeof(struct%20tNode))%3B%0A%20%20tNode-%3Edata%20%3D%20data%3B%0A%20%20tNode-%3Eleft%20%3D%20NULL%3B%0A%20%20tNode-%3Eright%20%3D%20NULL%3B%0A%20%0A%20%20return(tNode)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%0A%20%20%2F*%20Constructed%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%20%20*%2F%0A%20%20struct%20tNode%20*root%20%3D%20newtNode(1)%3B%0A%20%20root-%3Eleft%20%20%20%20%20%20%20%20%3D%20newtNode(2)%3B%0A%20%20root-%3Eright%20%20%20%20%20%20%20%3D%20newtNode(3)%3B%0A%20%20root-%3Eleft-%3Eleft%20%20%3D%20newtNode(4)%3B%0A%20%20root-%3Eleft-%3Eright%20%3D%20newtNode(5)%3B%20%0A%20%0A%20%20MorrisTraversal(root)%3B%0A%20%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
4 2 5 1 3<\/pre>\n","protected":false},"excerpt":{"rendered":"
 Inorder Tree Traversal without recursion and without stack! – Using Morris Traversal, we can traverse the tree without using stack and recursion.<\/p>\n","protected":false},"author":1,"featured_media":31279,"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-27659","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\/27659","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=27659"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27659\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31279"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27659"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27659"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27659"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}