c++ - binary tree traversal why need to check pre->right != current

Question

In a binary tree traversal algorithm like below cited from this question, why do we need to check the second condition pre->right != current? is this a loop condition? when would this happen?

  pre = current->left;
  while(pre->right != NULL && pre->right != current)
    pre = pre->right;

Answer 1

Because the latter code makes a cycle (i.e. child pointing to a parent):

pre->right = current;

The cycle is deleted later, however, but the pre->right != current test tris to avoid following the cycle endlessly.

Answer 2

Consider the tree given below,

    A
   / \
  B   C
 / \  /\
D  E F  G

The node A which is the root is initialized as current. Now the code given by you tries to find out the immediate predecessor of A in inoreder traversal. As we know the inorder traversal of the given tree is as follows,

D  B  E  A  F  C  G 

So the code identifies E as the immediate predecessor of A.

Answer 3

[Pertaining to your Question-code]
Assume tree:

   A
  / \
 B   C

It's In-order traversal = B,A,C

Now consider, B was already printed by

if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }

So, The Condition:

pre->right != current

is required to break while loop (which may be cyclic at times), exactly when our aim is to print node A.

In this case, at the end of the while loop i.e. while(pre->right != NULL && pre->right != current), we'll have :

1) pre pointing to left node B - which is already printed
2) current pointing to middle node A - Next to be print, thus breaking cycle link we've created just for this. Following part takes care of this:

else
      {
        pre->right = NULL;           // Break cyclic link we've created for printing 'A'
        printf(" %d ",current->data);// prints 'A'
        current = current->right;    // Now, Aim for 'C'
      }