I am working with BSTs, and the node class must have a variable containing the depth of the node. How can I calculate this? The only way I can think of involves a recursive method to traverse the tree, but the problem is that I cannot return an int representing the depth, as the recursive method would have to return a node... any suggestions or better approaches?|||There is no reason a recursive method can't return an int!
pseudocode (since you did not specify a language)
-----------------------
int depth( Node n ) {
if (n.left != null %26amp;%26amp; n.right != null) {
return max( depth( n.left), depth( n.right)) + 1;
} else if (n.left != null) {
return depth( n.left) + 1;
} else if (n.right != null) {
return depth( n.left) + 1;
} else {
return 0;
}
}
-----------------------
I don't know of any way to calculate this without either:
- traversing the node's entire subtree (as above)
- calculating a trace path whenever a node is added or removed and recalculating the depths of every node on the trace path afterwords. This works best if the Node class actually stores its left and right depths separately and calculates depth "on demand", as "max(lDepth,rDepth)".
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment