inorder traversal without recursion and stack
//Pragram in C++ to do inorder traversal of binary tree without recursion and stack
//using morris inorder traversal
btree* find_predecessesor(btree *root){
btree *head = root;
root = root->left;
//go to rightmost node of left subtree
while(root->right && root->right != head){
root = root->right;
}
return root;
}
void morris_inorder(btree *root){
while(root){
if(!root->left){
//when left subtree is empty
cout<<root->data<<" ";
root = root->right;
} else{
btree *link = find_predecessesor(root);
if(link->right){
//if left subtree has already been traversed
link->right = NULL;
cout<<root->data<<" ";
root=root->right;
}
else{
//link predecessor node to current node
link->right = root;
root=root->left;
}
}
}
}