Tree depth?
Author
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) );
}
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.
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.
Author
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.
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.
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.
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;}
Author
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]
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]
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]
[edited by - iMalc on June 11, 2004 4:40:17 AM]
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
