Problem Statement:
Print inorder traversal of the tree without using extra space (Morris Traversal)
Given Binary Tree
Resultant Inorder Traversal:
Solution:
Morris Traversal is based on the concept of Threaded Binary Trees. In 1979 , Morris proposed this algorithm in his paper , "Traversing Binary Trees Simple and Cheaply" , i.e. without using any stack and keeping the orginal tree un-altered after the traversal is over.
A binary tree is Threaded by making every left child pointer point to the in-order predecessor of the node and every right child pointer point to the in-order successor of the node.
Advantages:
Morris traversal is an implementation of in-order traversal that uses threading:
Algorithm :
Full Source Code: LINK
Referernces: http://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading
Similar to this problem is in-order traversal using stack.
Please comment and post your suggestions or any critiques, they are most welcome. Feel free.
Happy Coding !! :)
Print inorder traversal of the tree without using extra space (Morris Traversal)
Given Binary Tree
Fig1: Given Binary Tree |
Fig2: Inorder Traversal of the given Tree |
Solution:
Morris Traversal is based on the concept of Threaded Binary Trees. In 1979 , Morris proposed this algorithm in his paper , "Traversing Binary Trees Simple and Cheaply" , i.e. without using any stack and keeping the orginal tree un-altered after the traversal is over.
A binary tree is Threaded by making every left child pointer point to the in-order predecessor of the node and every right child pointer point to the in-order successor of the node.
Advantages:
- Avoids recursion, which uses a call stack and consumes memory and time.
- The node keeps a record of its parent.
- The tree is more complex.
- It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.
Morris traversal is an implementation of in-order traversal that uses threading:
- Create links to the in-order successor
- Print the data using these links
- Revert the changes to restore original tree.
Algorithm :
copy root to current pointer
while current is not null
if current does not have left child
print current data
move to right
else
predessor = current's left child
while predessor's right is not null and predessor's right is not current pointer
// establishing link , i.e. predessor's right child is null
Make current as right child of the rightmost node in temp's left subtree
move to left
// breaking link , i.e. predessor's right child is current pointer
predessor's right = null
print current data
move current to right
Full Source Code: LINK
/** * Inorder Morris Traversal(Threaded Binary Concept used) * @author Prateek http://ideone.com/f3lN0T */ public void inorderMorrisTraversal(Node root){ if(root==null) return ; Node current=root; while(current!=null){ if(current.left == null) { System.out.println(current.data); current = current.right; } else { Node pre = current.left; while(pre.right != null && pre.right!=current) pre = pre.right; //pre = predessor of current node if(pre.right==null) //make the link { pre.right = current ; current = current.left; } else //Break the link { pre.right = null ; System.out.println(current.data); current = current.right; } } } }
Referernces: http://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading
Similar to this problem is in-order traversal using stack.
Please comment and post your suggestions or any critiques, they are most welcome. Feel free.
Happy Coding !! :)
Excellent approach! Although I can make small modification to print in-oder predecessor and revert thread, immediately without traversing same left again.
ReplyDeleteGood post! As far as I know in Binary Search Tree, in-order successor of the input node will also be defined as the node with the smallest key which is greater than the key of input node. So sometimes it’s important to search the next node in sorted order.
ReplyDelete