Recursion code question

[programgirl]

My question involves the bit of code in the function below called inOrder. I know the code works because I got it from a book and tested it, so that's not the problem.

I'm trying to map this function out on paper, but I don't understand how it can work if the second line keeps recursively calling the function again.

Assuming this is the bTree:

     1
   -3 2
  0 0 0 5

I'm thinking this happens:
1. pointer (1) does not equal to NULL
2. call inOrder (pass in the pointer to left)
3. pointer (-3) equals to NULL
4. since pointer equals to know, the if statement does not execute and nothing happens.

I know this is not right, but I don't see how. Could someone please walk me through the function?

Thanks so much.

struct node {
   int info;
   int *left;
   int *right;
};

class bTree {
  //various class methods not related to the question...
public: 
  void inOrderTraversal ();
private:
  void inOrder (int *);
  node *root;
};

void bTree::inOrderTraversal ()
{
  inOrder (root);
}

void bTree::inOrder (int *pointer)
{
  if (pointer != NULL) {
  inOrder (pointer ->left);
  cout << pointer -> info << "  ";
  inOrder (pointer ->right);
  }

}

[htirwin]

Does this make sense?

Basically you go left until you hit a dead end, then print, then go right, and repeat.

Each time you hit a null pointer, you return from the branch to the place where you branched from.

inOrder(1)
    inOrder(-3) //1's left
        inorder(-3's left)
            -3's left == null;
            return 
        print -3
        inorder(-3's right)
            3's right == null
            return
    print 1
    inorder(2) //1's right
        inorder(2's left)
            2's left == null
            return
        print 2
        inorder(5) //2's right
            inorder(5's left)
                5's left == null
                return
            print 5
            inorder(5's right)
                5's right == null
                return
    return

[firedraco]

I'm thinking this happens:
1. pointer (1) does not equal to NULL
2. call inOrder (pass in the pointer to left)
3. pointer (-3) equals to NULL
4. since pointer equals to know, the if statement does not execute and nothing happens.

I'm not sure what you mean by "pointer (-3) equals NULL." How can a NULL pointer have a (-3) in it?

This function looks wrong anyway, did you mean to have it take a node*?

A possible way to look at this would be to step through the function with a debugger so you can look at how the function is working and the arguments that

[htirwin]

I'm thinking this happens:
1. pointer (1) does not equal to NULL
2. call inOrder (pass in the pointer to left)
3. pointer (-3) equals to NULL
4. since pointer equals to know, the if statement does not execute and nothing happens.

pointer (-3) isn't null, it's member, "left" is a null pointer . inOrder(-3's -> left) is called, and quickly returns without doing anything, but it returns to just after the place it was called, which is the print statement where -3 is printed.

Then next line is inOrder(-3's right), which also does nothing because -3's right is a null pointer, and ends, returning to the place it was called, which is the end of recursive branch, and that branch returns to the place after where it was called, which is after inOrder(1), where 1 is printed, and then inOrder(1's right) is next, and so on...

[programgirl]

inOrder(-3's -> left) is called, and quickly returns without doing anything, but it returns to just after the place it was called, which is the print statement where -3 is printed.

This is exactly what I didn't understand: that it will return to just after the place it was called. That is very helpful thanks much. Now I can follow htriwin map of the function too, thanks everyone!

[cire]

http://ideone.com/QOlIcm

[Smac89]

That's pretty cool output cire

[programgirl]

cire that's so awesome thank you very much.

[programgirl]

i just had another thought though, what happens if one of the numbers in your binary tree is zero? Won't the computer confuse that with NULL?

[TinyTeeTree]

programgirl, lets set a couple of things straight.

1)

struct node {
   int info;
   int left;
   int right;
};

is incorrect, the left and right members should be pointers to node like so

struct node{
   int info;
   node * left;
   node * right;
};

in this manner each node has its own info, and a pointer to another node.

[programgirl]

in this manner each node has its own info, and a pointer to another node.

Yes, that is true, I did forget to put those in my code above. I also failed to put in my public function to assign the pointer to inOrder. I'll edit my code above to correct these errors.

[TinyTeeTree]

you are on your way, to greatness.