Assigning a depth to each node

I read a few other articles on here that looked similar, bu开发者_开发百科t 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);
    } 
}

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);
    }
}

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?

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).

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); } }

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.,

I have a slightly more complicated design with varying Node Types and did this, so i thought id share.

If you have a tree that varies in type Node to Node (Binary, Unary etc) it is worth simplifying the traditional method to avoid the nasty embedded IFs to check the Nodes type.

Two Functions:

• 1: From the root, run through each node and check its distance to the root by recursivly calling itself and adding 1 for each parent. Give each node a depth variable to store this.
• 2: From the complete set of Nodes in the tree run a MAX check against each nodes depth, the highest number will equal the depth of the tree.

Processing this way removes explicit type-checking and simply counts the Node no matter if it has one, two or a hundred children.

Hope this helps someone!