What is Morris traversal?
Morris traversal is used to traverse through binary tree without using stack or recursion. Morris traversal is based on Threaded binary tree.
What is Threaded binary Tree
Threaded binary tree is similar to binary tree but it has one unique trait that is all the nodes whose right child points to NULL is diverted to point to its inOrder successor and all the nodes whose left child points to NULL is diverted to point its inOrder predecessor.
Morris Traversal types
It can be used to traverse all three kinds i.e
- PreOrder traversal
- InOrder traversal
- PostOrder traversal
Morris (InOrder) Traversal
Morris traversal in InOrder is just like binary tree InOrder traversal in which first we visit left subtree then, root node and at last right subtree. But in Morris Traversal while traversing we create links to inOrder successor and print the data using these links that we have made. But as we get done with particular node and if it has been connected through link then we break that connection and move forward. We do this thing to make sure that we do not disturb order of our original tree. And that is how we traverse through binary tree without using any extra space.
Let us consider following binary tree :
Let's see how to make links and how to restore tree by breaking those links
Consider we initiate current node as root node then we will check if left of current is NULL if it is then we will print current and we will move to right subtree part else now we will find right most node (node having its right pointer pointing to null or to current node) of left node if left node doesn't have any right node then it is itself a right node and we link it to current node else the moment we find right node we link it to the current node.(That is we make right pointer to point current node which was earlier pointing to NULL )
Now we are again at current node since we made link to it. Now we again check it has left node as we are taking above tree in consideration we know it does have left node and we made a link of its right most node just now. so again it will find right most (node having its right pointer pointing to null or current node) of left node and this time we will go till right most becomes current node once we get our right most node which is our current node we get that we have already made connection. Now we print data of our current node and make right most node NULL. Remember that we do not make current node NULL.
Now current moves to left subtree and similarly first 2 processes will be applied to our current node again.
Time Complexity : As we have seen at max a node might get visited 3 times so it has O(3n) = O(n) time complexity.
Space Complexity : As we do not use any extra space its space complexity is O(1).