Morris inorder traversal - binary tree

May 26, 2015

Problem Statement: 

Print inorder traversal of the tree without using extra space (Morris Traversal)

Study two websites:

1. http://codingrecipies.blogspot.ca/2013/11/morris-inorder-traversal.html

Implement the code using C#, and use the same example in the above website.

2. http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Here is the short description to understand the algorithm:

Concept Involved: 

Morris traversal is an implementation of in-order traversal that uses threading:

1.    Create links to the in-order successor

2.    Print the data using these links

3.    Revert the changes to restore original tree.

Here is the C# code:

https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs

read the blog (July 9, 2015):

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html#3171669