#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2013
    Posts
    33
    Rep Power
    0

    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));
    }
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    Also here
    Pick ONE forum and stick to it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2013
    Posts
    33
    Rep Power
    0
    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.
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2013
    Posts
    33
    Rep Power
    0
    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

    • ptr2void disagrees : Unrepentant help vampire
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2013
    Posts
    40
    Rep Power
    19
    :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 
    }

IMN logo majestic logo threadwatch logo seochat tools logo