Program for inorder traversal without implicit or explicit stack.

Here is the program for performing inorder traversal on a tree without implicit or explicit stack.

void BST::InOrderWithoutStack() {

BSTNode * p = root, *tmp;

while (p != 0)

if (p->left == 0) {

visit(p);

p = p->right;

}

else{

tmp = p->left;

while( tmp->right != 0 && tmp->right != p)

tmp = tmp->right;

if(tmp->right == 0) {

tmp->right = p;

p = p->left;

}

else {

visit(p);

tmp->right = 0;

p = p->right;

}

}

}

Subtle information in this algorithm to be noticed is that once the succesor nodes are pointed by the rightmost node of the left child, the tree looses its structure by having cycle in it.

And further when these nodes are traversed then this code

else {

visit(p);

tmp->right = 0;

p = p->right;

}

will make it as a tree by removing the cycle.