Inorder Tree Traversal without recursion and without stack ?

To traverse the tree using Morris Traversal is based on Threaded Binary Tree which means without using stack and recursion. 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.

- If current does not have left child
  - Print current’s data
  - Go to the right, i.e., current = current->right

- Else
  - Make current as right child of the rightmost
  - node in current’s left subtree
  - Go to this left child, i.e., current = current->left

When 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.

Sample Code in C++

[pastacode lang=”cpp” manual=”%23include%20%3Cstdio.h%3E%20%0A%23include%20%3Cstdlib.h%3E%20%0A%0A%2F*%20A%20binary%20tree%20tNode%20has%20data%2C%20pointer%20to%20left%20child%20%0Aand%20a%20pointer%20to%20right%20child%20*%2F%0Astruct%20traversalNode%20%7B%20%0A%09int%20data%3B%20%0A%09struct%20traversalNode*%20left%3B%20%0A%09struct%20traversalNode*%20right%3B%20%0A%7D%3B%20%0A%0A%2F*%20Function%20to%20traverse%20binary%20tree%20without%20recursion%20and%20%0Awithout%20stack%20*%2F%0Avoid%20MorrisTraversal(struct%20traversalNode*%20root)%20%0A%7B%20%0A%09struct%20traversalNode%20*current%2C%20*pre%3B%20%0A%0A%09if%20(root%20%3D%3D%20NULL)%20%0A%09%09return%3B%20%0A%0A%09current%20%3D%20root%3B%20%0A%09while%20(current%20!%3D%20NULL)%20%7B%20%0A%0A%09%09if%20(current-%3Eleft%20%3D%3D%20NULL)%20%7B%20%0A%09%09%09printf(%22%25d%20%22%2C%20current-%3Edata)%3B%20%0A%09%09%09current%20%3D%20current-%3Eright%3B%20%0A%09%09%7D%20%0A%09%09else%20%7B%20%0A%0A%09%09%09%2F*%20Find%20the%20inorder%20predecessor%20of%20current%20*%2F%0A%09%09%09pre%20%3D%20current-%3Eleft%3B%20%0A%09%09%09while%20(pre-%3Eright%20!%3D%20NULL%20%26%26%20pre-%3Eright%20!%3D%20current)%20%0A%09%09%09%09pre%20%3D%20pre-%3Eright%3B%20%0A%0A%09%09%09%2F*%20Make%20current%20as%20right%20child%20of%20its%20inorder%20%0A%09%09%09predecessor%20*%2F%0A%09%09%09if%20(pre-%3Eright%20%3D%3D%20NULL)%20%7B%20%0A%09%09%09%09pre-%3Eright%20%3D%20current%3B%20%0A%09%09%09%09current%20%3D%20current-%3Eleft%3B%20%0A%09%09%09%7D%20%0A%0A%09%09%09%2F*%20Revert%20the%20changes%20made%20in%20if%20part%20to%20restore%20%0A%09%09%09the%20original%20tree%20i.e.%2C%20fix%20the%20right%20child%20%0A%09%09%09of%20predecssor%20*%2F%0A%09%09%09else%20%7B%20%0A%09%09%09%09pre-%3Eright%20%3D%20NULL%3B%20%0A%09%09%09%09printf(%22%25d%20%22%2C%20current-%3Edata)%3B%20%0A%09%09%09%09current%20%3D%20current-%3Eright%3B%20%0A%09%09%09%7D%20%2F*%20End%20of%20if%20condition%20pre-%3Eright%20%3D%3D%20NULL%20*%2F%0A%09%09%7D%20%2F*%20End%20of%20if%20condition%20current-%3Eleft%20%3D%3D%20NULL*%2F%0A%09%7D%20%2F*%20End%20of%20while%20*%2F%0A%7D%20%0A%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Helper%20function%20that%20allocates%20a%20new%20tNode%20with%20the%20%0Agiven%20data%20and%20NULL%20left%20and%20right%20pointers.%20*%2F%0Astruct%20traversalNode*%20newtraversalNode(int%20data)%20%0A%7B%20%0A%09struct%20traversalNode*%20node%20%3D%20new%20traversalNode%3B%20%0A%09node-%3Edata%20%3D%20data%3B%20%0A%09node-%3Eleft%20%3D%20NULL%3B%20%0A%09node-%3Eright%20%3D%20NULL%3B%20%0A%0A%09return%20(node)%3B%20%0A%7D%20%0A%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%20%0A%7B%20%0A%0A%09%2F*%20Constructed%20binary%20tree%20is%20%0A%09%09%0912%20%0A%09%09%2F%20%5C%20%0A%09%0913%09%2014%20%0A%09%2F%20%5C%20%0A%0915%09%2016%20%0A*%2F%0A%09struct%20traversalNode*%20root%20%3D%20newtraversalNode(12)%3B%20%0A%09root-%3Eleft%20%3D%20newtraversalNode(13)%3B%20%0A%09root-%3Eright%20%3D%20newtraversalNode(14)%3B%20%0A%09root-%3Eleft-%3Eleft%20%3D%20newtraversalNode(15)%3B%20%0A%09root-%3Eleft-%3Eright%20%3D%20newtraversalNode(16)%3B%20%0A%0A%09MorrisTraversal(root)%3B%20%0A%0A%09return%200%3B%20%0A%7D%20″ message=”” highlight=”” provider=”manual”/]

Output

15 13 16 12 14

Time Complexity : O(n) If we investigate, we can see that each edge of the tree is crossed at-most multiple times.
Also, in most pessimistic scenario same number of additional edges (as info tree) are made and evacuated.

Inorder Tree Traversal without recursion and without stack ?