Binary Tree Depth Problem

Answer 1

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?

Answer 2

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 3

int assignDepth(Tree &T, int depth)

You have defined Tree as a pointer to a treeNode. You don't need to pass it by reference. You can modify the node that's pointed to anyway.

{
    if(T!=NULL)
    {
        depth = assignDepth(T->left, depth++);

The postfix ++ ensures that you're passing the original depth down. That's not what you want. Increment depth before this, and forget about returning it as a function result.

    T->depth = depth;

This is OK.

        depth = assignDepth(T->right, depth++);

Similar as for the previous recursive call, except that here you shouldn't modify depth at all because it has already been incremented.

    }
  else //leaf
        return depth--;

You don't need to return any depth information (or is that an unstated requirement?).

}

Cheers & hth.,

Answer 4

1. Once you've reached a leaf node, you don't care about its depth any more, so the return value appears to accomplish nothing.

2. In two statements:

   depth = assignDepth(T->left, depth++);
   // and
   depth = assignDepth(T->right, depth++);
   

You have undefined behavior from modifying depth twice without an intervening sequence point (although it seems like there should be, there is not a sequence point between the right and left sides of an assignment).

Answer 5

1. Why are you returning when the node is NULL. As per your specification you don't need to return any depth

2. In other case you just need to increment the depth and send to the function call. The following is my version of the code

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