Like Tree2Likes
  • 1 Post By oogabooga
  • 1 Post By vart

Distance between root and leaf.

This is a discussion on Distance between root and leaf. within the C Programming forums, part of the General Programming Boards category; Hi, I wrote the following recursion for finding the distance between a root and a leaf, but am not quite ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    122

    Distance between root and leaf.

    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));
    }

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    What do you want to test in the line 5?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    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));
    }

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    But it still would not work. Why is that?

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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?
    iMalc likes this.

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    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...
    iMalc likes this.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    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.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    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.

  9. #9
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    looks like the result will be 1 if leaf is present in the tree and 0 otherwise
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    The leaf is certainly in the tree. Question is - what would be the shortest path to it.
    Hmm... How about this:
    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));
    }
    But again, even if that were to work, it would still not quite return the shortest distance, right?

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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!)

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    Quote Originally Posted by peripatein
    The leaf is certainly in the tree. Question is - what would be the shortest path to it.
    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.

    Hence, to find the path, you would start from the root and search for the leaf, which is what oogabooga described in post #11.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    May 2012
    Posts
    331
    Quote Originally Posted by peripatein View Post
    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));
    }
    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;
    }
    This searches virtually the whole tree, so it's not the most efficient way of doing it. But it's easy.
    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.
    http://www.malcolmmclean.site11.com/www

  14. #14
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    This searches virtually the whole tree, so it's not the most efficient way of doing it.
    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.

    And it's best not to just post a solution. Anyone here can do that.

  15. #15
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    actually it could be slightly optimized
    Code:
       ldepth = calc_depth(root->left, node);
       if(ldepth)
         return ldepth + 1;
       rdepth = calc_depth(root->right, node);
       if(rdepth)
         return rdepth +1;
    no need to traverse right tree if already found on the left
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. HELP! :linked list from tree leaf nodes
    By ayman88 in forum C Programming
    Replies: 2
    Last Post: 02-28-2010, 11:19 PM
  2. building a linked list from tree leaf nodes
    By ayman88 in forum C Programming
    Replies: 0
    Last Post: 02-27-2010, 03:24 PM
  3. Distance to City
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 08-17-2003, 10:58 PM
  4. Hex distance
    By waterst in forum C Programming
    Replies: 7
    Last Post: 11-02-2002, 12:59 PM
  5. love and distance
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 02-19-2002, 12:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21