# Morris InOrder Tree Traversal, Tree Traversal without using extra space and without recursion

We have the regular tree traversals that uses either recursion (function stack), or intentionally created stack to do the traversal in iterative way. But what do we do when we need to do a tree traversal without any extra space and without recursion.
Lets first think this way, iterative way is possible if we create a stack (this is a regular way). If we give some thought, we need stack for storing the in-order successor, we push the current node into stack and move to left, when we come back , we pop this node and print, and then move right.
Can we think of getting to this node back by some way. Does Threaded Binary Tree ring any bells? Yes, we can create threads back to the in-order successor, and in this way we will get to use the space (null pointers) of leaf nodes, and wont be needing any extra space.

So, Morris InOrder Traversal uses Threads instead of stack to get to the in-order successor. In this traversal, we first create threads to in-order successor, and print the nodes, and by the end we revert back the changes made to tree, i.e we remove all the additional threads we created in the process. Point to be noted is that, tree is modified in between, but by the end of traversal, original tree is restored.

```Algorithm:
take root node into new node temp
while temp is not null
if temp does not have left child
print temp data
move to right
else
Make temp as right child of the rightmost node in temp's left subtree
move to left
```

Here’s the C++ code

```//Binary Tree
typedef struct bTree{
int data;
bTree *left,*right;
}bTree;
//MORRIS INORDER TRAVERSAL, pass the root node as argument
void morris(bTree *ptr){
//testing part :P
if(!ptr){
return;
}
// we do have a genuine bTree

bTree *temp;//temp pointer

//loop till ptr is null
while(ptr){
// if ptr left is null
if(!ptr->left){
//print the data
printf("[%d]",ptr->data);
//move right
ptr=ptr->right;
}else{//has a left pointer

//Find the inorder predecessor of current node
temp = ptr->left;
while(temp->right && temp->right!=ptr){
temp=temp->right;
}

//Make current node as right child of its inorder predecessor
if(!temp->right){
temp->right=ptr;
ptr=ptr->left;
}else{
// Revert the changes to restore the original tree
temp->right = NULL;//make it the way it was earlier, i.e null
printf("[%d]",ptr->data);
ptr=ptr->right;
}

}//end if else
}//end while
}//end func morris

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5d8038152c307',  {
collapseEmpty: 'before',
sectionId: '26942',
location: 120,
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5d8038152c30c',  {
collapseEmpty: 'before',
sectionId: '114160',
location: 130,
width: 300,
height: 250
});
});

```