Depth assignment for each node

Question

I read a few more articles that looked similar, but didn’t quite answer my problem. I was asked about the assignment to assign each node in the binary tree the corresponding depth. I just can't 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 to start it with a pen and paper, and everything looked fine, but I obviously lacked the skills to check the table.

Can someone point me in the right direction please? This is my first time using trees, and recursion is not my forte.

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 do not need

 else //leaf return depth--; 

You also do not want to increase the depth variable, just go through a depth of + 1 until the next internment.

There is also no need to return a value.

Try the following:

 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 use post-increment / decment, you probably meant ++depth/--depth for the correct assignment, and else came back;

Also, why pass a pointer as a reference variable?

Answer 3

 int assignDepth(Tree &T, int depth) 

You defined Tree as a pointer to treeNode . You do not need to pass it by reference. You can change the node that pointed to anyway.

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

Postfix ++ ensures that you pass the original depth down. This is not what you want. Increment depth to this, and forget about returning it as a result of the function.

  T->depth = depth; 

This is normal.

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

Similar to the previous recursive call, except that here you should not change the depth at all, because it has already been increased.

  } else //leaf return depth--; 

You do not need to return any depth information (or is this an undefined requirement?).

 } 

Cheers and hth.,

Answer 4

• Once you reach the node sheet, you no longer care about its depth, so the return value will do nothing.

• In two statements:

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

You have undefined behavior when modifying depth twice without an intermediate sequence point (although it seems like it should be, there is no sequence point between the right and left sides of the destination).

Answer 5

• Why are you coming back when node is NULL. According to your specification, you do not need to return any depth.

• Otherwise, you just need to increase the depth and send a function call. Below is my version of the code

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

Answer 6

I have a slightly more complex design with various types of Node and did it, so I thought I had a share id.

If you have a tree that changes from Node type to Node (binary, unary, etc.), it’s worth simplifying the traditional method to avoid the unpleasant built-in IFs for checking the type of Nodes.

Two functions:

• 1: from the root, go through each Node and check its distance to root by recursively calling yourself and adding 1 for each parent. Give each Node a depth variable to save it.
• 2: from a complete set of nodes in the tree, perform a MAX check against each depth of nodes, the largest number will be equal to the depth of the tree.

Processing this method removes explicit type checking and simply counts Node regardless of whether it has one, two, or hundreds of children.

Hope this helps someone!