Tree Traversal in O(1) Auxilary Space

Hey everyone, Today I am going to share a tree traversal algorithm that is somewhat different from the traditional traversal algorithm. Generally, traditional traversal algorithm uses a time Complexity of O(n) and Auxiliary Space complexity of order O(n) . But these algorithm uses the time Complexity of order O(n) and Auxiliary Space complexity of order O(1). Can you make any guess about the algorithm ? The algorithm used is known as Morris Traversal. I came across this algorithm while solving a Binary Search Tree problem .

Morris Traversal - Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors, and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.

The algorithm of the Morris(inorder) Traversal is as follows

1. Initialize the root as the current node curr.
2. While curr is not NULL, check if curr has a left child.
3. If curr does not have a left child, print curr and update it to point to the node on the right of curr.
4. Else, make curr the right child of the rightmost node in curr's left subtree.
5. Update curr to this left node.

this article talks about how to get the inorder traversal of a tree using Morris Traversal . We can further extend it to get the pre-order and post-order traversal of a tree

link for the original article click here

link for the question click here

Thanks for reading the article till the end, all suggestions are welcomed :)