Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Tree depth?

This topic is 5093 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How to determine tree depth when using a stack, instead of recursively traversing a tree? I need to keep track of it. Does the depth need to be saved in the stack? Something that I want to avoid. // just an example of how I keep track of tree depth using recursive functions void Recursive_Depth(TREE_NODE *node, INT depth ) { Recursive_Depth( node, (depth+1) ); }

Share this post


Link to post
Share on other sites
Advertisement
Smells like homework.

For a hint: consider what the hardware stack looks like (number of active invocations of the function at each point in time) over the course of the recursive function.

Share this post


Link to post
Share on other sites
No, it''s not homework, and I''m looking for answers, not hints.

If you''re implying that the number of items pushed onto the stack is related to the tree depth, then I think that''s not correct.

Share this post


Link to post
Share on other sites
I am not exactly sure what you mean by keeping the tree depth using a stack. Do you mean, having a key/value pair stack, where the keys are depths, and the values are all the nodes at that level? I think I would rather just use the recursive depth function, or have a depth variable of the nodes, where I would just increment the parent''s depth, if a parent exists, that and I think it would be more efficent to do it that way, if you are just checking an individual node''s depth.

Share this post


Link to post
Share on other sites
You do it the same way, except where you''d normally have a recursive function call, you push stuff on the stack, and when you''d normally return from a function call, you pop stuff off the stack. It goes something like this:

int TreeDepth(TREE_NODE *node)
{
int maxDepth = 0;

stack<TREE_NODE *> nodeStack;
stack<int> depthStack;

nodeStack.push(node);
depthStack.push(0);

while(!nodeStack.empty())
{
TREE_NODE *curNode = nodeStack.top();
int curDepth = depthStack.top();

nodeStack.pop();
depthStack.pop();

if(curDepth > maxDepth)
maxDepth = curDepth;

if(curNode->left != NULL)
{
nodeStack.push(curNode->left);
depthStack.push(curDepth + 1);
}

if(curNode->right != NULL)
{
nodeStack.push(curNode->right);
depthStack.push(curDepth + 1);
}
}

return maxDepth;
}

Share this post


Link to post
Share on other sites
Well, lack of memory could be a problem for me, so I'm just trying to come up with the smallest
memory requirement for a stack + tracking depth. If there was some way to keep track of tree
depth without saving it in each stack node, then I could save myself 4 bytes per node, but
I guess it's not possible.

bastard2k5,
The point of using a stack instead of a recusive function is to prevent program crashes.

[edited by - raydog on June 10, 2004 10:16:17 PM]

Share this post


Link to post
Share on other sites
If you use an AVL-Tree then finding the depth is as easy as querying the root node. This also has the advantage of always being balanced. If you're using a tree as opposed to a linked list then I assume you are doing it for performance reasons, in which case use an AVL-Tree, problem solved!

[edited by - iMalc on June 11, 2004 4:40:17 AM]

Share this post


Link to post
Share on other sites
Maybe you could look into other parts of your program for saving memory space. I doubt that the stack is going to be your biggest memory usage.

Perhaps if you tell us more about the amount of memory you actually have available and what your program does etc, posters may be able to help you more effectively towards your goal.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!