Binary Search Trees - InOrder Traversal

[waelali]

Hi,

I have a big problem to understand the recusrsive way of implementing InOrder Traversal - BST.

Lets have a look:

void inorderTraversal( Node root ){
    if( root == null ) return;
    inorderTraversal( root.getLeft() );
    root.printValue();
    inorderTraversal( root.getRight() );
}

Recursion is not easy to understand , for me at least :-). Having one nested function which is called recursively is not difficult to understand, but when I look to the previous code , and see:


inorderTraversal( root.getLeft() ); and also inorderTraversal( root.getRight() ); and between them root.printValue();



This makes me crazy.

Assume that we have the following BST

       X
     /   \
    Y     Z
   / \   / \
   W  P Q  R

1. Can someone tell me how the InOrder is executed step by step??
2. What is the execution order of the recursive functions??
3. Can you please provide a stack diagram , which illustrates all that?? - That will help me to visualize the problem and the solution more.

Thank you

[waelali]

No one can answer??

[jsmith]

The function is rather simple. Line 2 says to stop recursing when you hit a leaf node.
The next three lines say to first process the left child, then the current node, then the right child.

So inorderTraversal gets called on X. Line 3 says to call itself on Y. Line 3 then says to call itself on W. Line 3 then says to call itself on W's left child (which is NULL). Etc.

[waelali]

I know all of these things, it is kind of question that many people can solve , but not all know what are the steps there .. How the stack is really built , and what points and calls are done into the stack, and how the popup operations are done and in what order.

That what I meant when I asked...


Lets see the code again ,

void inorderTraversal( Node root )
{
    if( root == null ) return;
    inorderTraversal( root.getLeft() );
    root.printValue();
    inorderTraversal( root.getRight() );
}

and the tree:-

   
       X
     /   \
    Y     Z
   / \   / \
 W  P Q  R 

The traversal order - output is : W Y P Q Z R X ( Is it right ?? )


1. I need a stack diagram that explains how the calls are done and popup is done , in order to understand the call order of the recursions...

Thank you

[jmc]

inorderTraversal(X);
  inorderTraversal(Y);
    inorderTraversal(W);
      inorderTraversal(NULL); // abort node since NULL
      root.printValue();      // print W
      inorderTraversal(NULL); // abort node since NULL
    root.printValue();        // print Y
    inorderTraversal(P);
      inorderTraversal(NULL); // abort node since NULL
      root.printValue();      // print P
      inorderTraversal(NULL); // abort node since NULL
  root.printValue();          // print X
  inorderTraversal(Z);
    inorderTraversal(Q);
      inorderTraversal(NULL); // abort node since NULL
      root.printValue();      // print Q
      inorderTraversal(NULL); // abort node since NULL
    root.printValue();        // print Z
    inorderTraversal(R);
      inorderTraversal(NULL); // abort node since NULL
      root.printValue();      // print R
      inorderTraversal(NULL); // abort node since NULL 

If that is not what you want (I couldn't believe if it was ;)) then you should perhaps be a little more specific about your question. I u can't understand how it works jump at a function call always at the first line and when the function is aborted (by return or end of function) jump back where u were before that call. That is more or less what your computer does. Additionally it will most probably put the current values on the stack at the beginning and pop them again at the end of each call of your function.

[waelali]

Thank you , but I still have something to understand.

Have a look on your post on lines 7,8,9,10,11

    root.printValue();        // print Y
    inorderTraversal(P);
      inorderTraversal(NULL); // abort node since NULL
      root.printValue();      // print P 

and have a look on the function also

void inorderTraversal( Node root )
{
    if( root == null ) return;
   (1)  inorderTraversal( root.getLeft() );
   (2)  root.printValue();
   (3)  inorderTraversal( root.getRight() );
}

after printing 'Y' by calling root.printValue(); , the function continues to the next statement inorderTraversal( root.getRight() ); , and calls P , so we have now inorderTraversal(P);

what now?? P has no leafs , both are NULL. Do we now call the NULL on the left leave of P or NULL on the right leave??

Let me say that in different way :-), when we arrive to P, so we are on statement number (3) , since it is on right, then we stay call on statement (3) , inorderTraversal(p->right), which is inorderTraversal(NULL) - Go back - call is terminated .... the questions where we go back now ? is it to statement (1), and call inorderTraversal(p-->left) , which is inorderTraversal(NULL), and then print P??

Thank you

[jmc]

I'll write you an inline version from the point where inorderTraversal(Y) is called. Maybe that will help you:

// start call inorderTraversal(X.getLeft()) == inorderTraversal(Y)
  if(Y == NULL){ // doesn't abort since Y != NULL
    return;
  }

  // start call inorderTraversal(Y.getLeft()) == inorderTraversal(W)
    if(W == NULL){ // doesn't abort since W != NULL
      return;
    }
     // start call inorderTraversal(W.getLeft()) == inorderTraversal(NULL)
       if(NULL == NULL){ // since W's got no nodes W.getLeft() == NULL
         return; // abort here further code of this call isn't executed
       }
     // end call inorderTraversal(NULL)
     W.printValue(); // print W
     // start call inorderTraversal(W.getRight()) == inorderTraversal(NULL)
       if(NULL == NULL){ // since W's got no nodes W.getRight() == NULL
         return; // abort here further code of this call isn't executed
       }
     // end call inorderTraversal(NULL)
  // end call inorderTraversal(W)

   Y.printValue(); // print Y

  // start call inorderTraversal(Y.getRight()) == inorderTraversal(P)
    if(P == NULL){ // doesn't abort since P != NULL
      return;
    }
     // start call inorderTraversal(P.getLeft()) == inorderTraversal(NULL)
       if(NULL == NULL){ // since P's got no nodes P.getLeft() == NULL
         return; // abort here further code of this call isn't executed
       }
     // end call inorderTraversal(NULL)
     P.printValue(); // print P
     // start call inorderTraversal(P.getRight()) == inorderTraversal(NULL)
       if(NULL == NULL){ // since P's got no nodes P.getRight() == NULL
         return; // abort here further code of this call isn't executed
       }
     // end call inorderTraversal(NULL)
  // end call inorderTraversal(P)

// end call inorderTraversal(Y) 

[waelali]

Thank you :-) It is clear to me now