Assigning a depth to each node

Question

I read a few other articles on here that looked similar, but didn't quite answer my problem. I've been given a question for an assignment to assign every node in a binary tree its respective depth. I just can't quite get it.

For reference this is my code:

struct treeNode {
   int item;
   int depth;
   treeNode *left;
   treeNode *right;
};
typedef treeNode *Tree;

int assignDepth(Tree &T, int depth)
{
    if(T!=NULL)
    {
        depth = assignDepth(T->left, depth++);
        T->depth = depth;
        depth = assignDepth(T->right, depth++);
    }
    else //leaf
        return depth--;
}

I tried running it through with pen and paper and it looked OK, but my desk checking skills are clearly lacking.

Can anyone point me in the right direction, please? This is my first time using trees, and recursion isn't my strong point.

Answer:

void treecoords(Tree &T, int depth)
{
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values
    if(T!=NULL)
    {
        treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack
        count++;
        T->x = count;
          T->y = depth;
        treecoords(T->right, depth+1);
    } 
}

Answer 1

You don' t need

else //leaf
    return depth--;

You also don't want to increment the depth variable, just pass depth+1 to the next interation.

Also there's no need to return a value.

Try this:

void assignDepth(Tree T, int depth)
{
    if(T!=NULL)
    {
        assignDepth(T->left, depth+1);
        T->depth = depth;
        assignDepth(T->right, depth+1);
    }
}

Answer 2

Well, for starters, you're using post-increment/decrement, you probably meant ++depth/--depth for the right assignment and the else return;

Also, why pass a pointer as a reference variable?