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

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost 
         node in current's left subtree
      b) Go to this left child, i.e., current = current->left

Although the tree is modified through the traversal, it is reverted back to its original shape after the completion. Unlike Stack based traversal, no extra space is required for this traversal.

[pastacode lang=”c” manual=”%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” message=”” highlight=”” provider=”manual”/]

Output:

4 2 5 1 3

Categorized in: