{"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
 
 <\/div> 
#include<stdio.h>#include<stdlib.h> \/* A binary tree tNode has data, pointer to left child   and a pointer to right child *\/struct tNode{   int data;   struct tNode* left;   struct tNode* right;}; \/* Function to traverse binary tree without recursion and    without stack *\/void MorrisTraversal(struct tNode *root){  struct tNode *current,*pre;   if(root == NULL)     return;    current = root;  while(current != NULL)  {                     if(current->left == NULL)    {      printf("%d ", current->data);      current = current->right;          }        else    {      \/* Find the inorder predecessor of current *\/      pre = current->left;      while(pre->right != NULL && pre->right != current)        pre = pre->right;       \/* Make current as right child of its inorder predecessor *\/      if(pre->right == NULL)      {        pre->right = current;        current = current->left;      }                   \/* Revert the changes made in if part to restore the original         tree i.e., fix the right child of predecssor *\/         else       {        pre->right = NULL;        printf("%d ",current->data);        current = current->right;            } \/* End of if condition pre->right == NULL *\/    } \/* End of if condition current->left == NULL*\/  } \/* End of while *\/} \/* UTILITY FUNCTIONS *\/\/* Helper function that allocates a new tNode with the   given data and NULL left and right pointers. *\/struct tNode* newtNode(int data){  struct tNode* tNode = (struct tNode*)                       malloc(sizeof(struct tNode));  tNode->data = data;  tNode->left = NULL;  tNode->right = NULL;   return(tNode);} \/* Driver program to test above functions*\/int main(){   \/* Constructed binary tree is            1          \/   \\        2      3      \/  \\    4     5  *\/  struct tNode *root = newtNode(1);  root->left        = newtNode(2);  root->right       = newtNode(3);  root->left->left  = newtNode(4);  root->left->right = newtNode(5);    MorrisTraversal(root);   getchar();  return 0;}<\/code><\/pre> <\/div>\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}]}}