CareerCup

Morris Traversal

threaded binary tree representation helps with inorder tree traversal, without stacks - at minimum storing a space for flags for left and/or right thread for avoiding endless loops.

Another implementation without using stack is by storing an additional pointer to the parent per node - which is costly.

Thanks to abcd, found Morris traversal on StackOverflow. Didn't expect the structure can be modified. Elegant solution.

How about using array to store Binary Tree instead of nodes structure. And simply display the array.. This would be your inorder traversal only.

<pre lang="" line="1" title="CodeMonkey54817" class="run-this"> public void morisTravel(Node localRoot){

Node current=localRoot;

while(current!=null){

if(current.leftChild==null){
System.out.print(current.key+ " ");
current=current.rightChild;
}
else{
// Find Inorder predecessor
Node pre=current.leftChild;
while(pre.rightChild!=null && pre.rightChild!=current)
pre=pre.rightChild;

// Set Links
if(pre.rightChild==null){
pre.rightChild=current; //
current=current.leftChild; // Make current to predecessor of current
}
// Restore
else{
pre.rightChild=null;
System.out.print(current.key+" ");
current=current.rightChild;
}

}
}
}</pre><pre title="CodeMonkey54817" input="yes">Its moris travel algorithm. Create link to inorder successor for each leaf node. after traversing break it.Concept of threaded binary tree.
</pre>