June 20th, 2013, 12:40 AM
-
Distance between root and leaf.
Hi,
I wrote the following recursion for finding the distance between a root and a leaf in a binary tree, but am not quite sure how to make it work. Could anyone please advise?
Code:
int calc_depth(Node* root, Node* leaf)
{
if (!root)
return 0;
if (leaf->right == root || leaf->left == root)
return 1;
return (leaf->right ? calc_depth(root, leaf->right) : calc_depth(root, leaf->left));
}
June 20th, 2013, 12:52 AM
-
Also here
Pick ONE forum and stick to it.
June 20th, 2013, 12:59 AM
-
Originally Posted by salem
Also
here
Pick ONE forum and stick to it.
Why should I limit myself to one forum? Different groups, different people, different rationales/opinions etc.
June 20th, 2013, 01:26 AM
-
read this FAQ - all of it
If your question on two forums gets the SAME answer twice in both places, then someone completely WASTED their time reading and answering your post.
FREE time is a valuable resource you shouldn't be idly wasting. Now consider that someone else's post may in fact go unanswered because of you - do you still feel good about it?
You're getting FREE support here, the last thing you should be doing is provably wasting peoples time by this selfish "my post is very important, it deserves to be cross-posted" attitude.
June 20th, 2013, 02:55 AM
-
There is really no attitude! I see it this way, not only is this a very simple, straightforward question which should certainly not consume much time, but there are enough qualified people on both forums together to provide answers to all questions. It is rather rare that a question is left unanswered, and if it so happens it is even far more rare that it is because someone posted a simple question like mine elsewhere. If it means that much to you, I could remove it. But please note that I find this somewhat unnecessary and petty (no offense).
Comments on this post
June 20th, 2013, 03:46 AM
-
:cool:
Just thinking. At the root, you got depth = 0. You ask dept from left, how far from leaf it is. You ask the right too. Somewhere is your leaf...If found, return 1 and plus 1 for founder.
Pseudo code:
Code:
howdepth(root, leaf)
{
if ( leaf found) return 1
left_depth = 0
if (left_node !=NULL)
d = howdepth( left_node, leaft)
if (d >0 )
left_depth = 1+d
end if
end if
right_depth = 0
if ( right_node !=NULL)
d = howdepth( right_node, leaft)
if (d >0)
right_depth = 1+d
end if
end if
depth = max(left_depth, right_depth)
return depth
}