Hi,
I wrote the following recursion for finding the distance between a root and a leaf, but am not quite sure how to make it work. Could anyone advise?
Code:int calc_depth(Node* tree, Node* zero) { if (!tree) return 0; if (zero->right || zero->left == tree) return 1; return (zero->right ? calc_depth(tree, zero->right) : calc_depth(tree, zero->left)); }
What do you want to test in the line 5?
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
Silly me. Should have been:
Code:int calc_depth(Node* tree, Node* zero) { if (!tree) return 0; if (zero->right == tree || zero->left == tree) return 1; return (zero->right ? calc_depth(tree, zero->right) : calc_depth(tree, zero->left)); }
But it still would not work. Why is that?
The biggest problem is that you're not adding anything up. Think about it: the only thing that can possibly be returned from your function is 0 or 1, no matter how big the tree is.
And what is "zero"? Why are you comparing it to "tree"?
You should post your entire test program.
BTW, you haven't specified exactly what type of tree you're dealing with here. Obviously it's a binary tree, but is it arbitrary? complete? balanced?
also I do not understand in line 7 how you decide where the leaf will be in the right sub-tree or in the left sub-tree.
Looks to me you always go to the right if it exists, even if the leaf will be found on the left...
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
OK, is this better?:
Code:int calc_depth(Node* root, Node* leaf) { if (!root) return 0; return (leaf->right == root || leaf->left == root ? 1 : calc_depth(root, leaf->right) + calc_depth(root, leaf->left)); }
Last edited by peripatein; 06-20-2013 at 02:15 AM.
But of course that would go through all the leaves, without actually determining the shortest path, wouldn't it?
PS It is the most general binary tree. Nothing else is specified.
Last edited by peripatein; 06-20-2013 at 02:33 AM.
looks like the result will be 1 if leaf is present in the tree and 0 otherwise
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
The leaf is certainly in the tree. Question is - what would be the shortest path to it.
Hmm... How about this:
But again, even if that were to work, it would still not quite return the shortest distance, right?Code:int calc_depth(Node* root, Node* leaf) { int depth = 0; if (!root) return 0; return (leaf->right == root || leaf->left == root ? 1 : depth + calc_depth(root, leaf->right) + calc_depth(root, leaf->left)); }
You're digging down into the tree with the wrong input variable. Assuming that root is the top of the tree and leaf is the leaf you're looking for, then you need to search down with root->left and root->right. (If leaf is really a "leaf", then it's left and right pointers are NULL!)
There is only one path from the root to the leaf (or indeed any node), otherwise the structure is not a tree. Hence, the question of what is the shortest path to it is trivial to answer: the path to the leaf is the shortest path.Originally Posted by peripatein
Hence, to find the path, you would start from the root and search for the leaf, which is what oogabooga described in post #11.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
This searches virtually the whole tree, so it's not the most efficient way of doing it. But it's easy.Code:/* calculate the depth of node node. Tree has members right and left */ int calc_depth(Node *root, Node *node) { int ldepth, rddepth; if(root == 0) return 0; if(root == node) return 1; ldepth = calc_depth(root->left, node); rdepth = calc_depth(root->right, node); if(ldepth) return ldepth + 1; if(rdepth) return rdepth +1; /* node not on this sub-branch */ return 0; }
I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
Visit my website for lots of associated C programming resources.
https://github.com/MalcolmMcLean
If the tree has no structure besides being binary (as the OP has indicated), then there's no more efficient way than searching the whole tree.This searches virtually the whole tree, so it's not the most efficient way of doing it.
And it's best not to just post a solution. Anyone here can do that.
actually it could be slightly optimized
no need to traverse right tree if already found on the leftCode:ldepth = calc_depth(root->left, node); if(ldepth) return ldepth + 1; rdepth = calc_depth(root->right, node); if(rdepth) return rdepth +1;
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
