Morris traversal for Inorder

Morris traversal is a type of tree traversal algorithm that can be used to perform an in-order traversal of a binary tree without using recursion or a stack data structure. The Morris traversal algorithm achieves this by modifying the structure of the tree itself during the traversal process.

During the Morris traversal of a binary tree in in-order fashion, at each node, we first establish a temporary link from the rightmost node of the left subtree to the current node. This link, also known as a threaded link or thread, allows us to visit the left subtree without using a stack or recursion. After visiting the left subtree, we follow the thread back to the current node and visit it. Then, we establish a similar thread from the current node to the leftmost node of its right subtree and move to that node. We repeat this process until we have visited all nodes in the tree.

By using threads instead of a stack or recursion, the Morris traversal algorithm achieves a space complexity of O(1), which is more efficient than the O(h) space complexity of other in-order traversal algorithms, where h is the height of the tree. However, the Morris traversal algorithm modifies the structure of the tree during the traversal process, which may not be desirable in some cases.