Thread: Recursion for the ACTUAL maximum depth of a BT.

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

    Recursion for the ACTUAL maximum depth of a BT.

    Hi,
    I wrote the following function to determine the maximum depth of a binary tree, but it feels somewhat cumbersome to me. I'd truly appreciate it if you could help me improve it (make it shorter if possible and more elegant), albeit it works great:
    Code:
    int findMaxDepth(Node * tree, int curr){
        int left, right;
        if (!tree)
            return 0;
        right = findMaxDepth(tree->right, curr + 1);
        left = findMaxDepth(tree->left, curr + 1);
        curr = (curr > right) ? curr : right;
        return (left > curr ? left : curr);
    }
    Any insightful comments will be highly appreciated! :-)

    PS All the variations thereof which I saw online, and in other sources, find the maximum depth + 1, not the ACTUAL maximum depth. The above function yields the actual depth as desired.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    I think I would have gone with this (untested) approach.
    Code:
    int findMaxDepth(Node * tree, int curr){
        int left, right;
        if (!tree)
            return curr;
        right = findMaxDepth(tree->right, curr + 1);
        left = findMaxDepth(tree->left, curr + 1);
        return (left > right ? left : right);
    }
    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.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    But that returns maxdepth + 1, and not the actual maxdepth.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Do you regard a single node with left and right both NULL as being 0-depth or 1-depth ?

    For me, it has depth 1.

    A completely empty tree (aka node *mytree = NULL) has a depth of 0.
    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.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    depth 0. I have tried your code and it gave 7 where it supposed to have given 6 (and whereas my code gave 6).

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Salem
    Do you regard a single node with left and right both NULL as being 0-depth or 1-depth ?
    Quote Originally Posted by peripatein
    depth 0.
    In that case, what is the depth of an empty tree?

    EDIT:
    Oh, but DADS defines depth as being a property of a node with respect to the root, rather than a property of the tree, in which case asking what is the depth of the tree does not make sense... but that was your question too
    Last edited by laserlight; 06-22-2013 at 11:13 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    It is given that in this section the tree could not be empty.
    I first coded it thus, but figured my above code suited better. What do you think?
    Code:
    int findMaxDepth(Node * tree){
    	if (!tree)
    		return -1;
    	return(1 + findMaxDepth(tree->right) >= 1 + findMaxDepth(tree->left) ? 1 + findMaxDepth(tree->right) : 1 + findMaxDepth(tree->left));
    }

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    I think it pointlessly calls findMaxDepth() more times than necessary.
    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.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    I could have used more variables, agreed. But how may I improve the function I opened this thread with?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by peripatein
    But how may I improve the function I opened this thread with?
    Maybe it would be clearer with an if-else chain instead:
    Code:
    int findMaxDepth(Node * tree, int curr){
        int left, right;
        if (!tree)
            return 0;
        right = findMaxDepth(tree->right, curr + 1);
        left = findMaxDepth(tree->left, curr + 1);
        if (right > curr)
            return right;
        else if (left > curr)
            return left;
        else
            return curr;
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    But other than that, can you come up with a more elegant/sophisticated code to yield the same output?
    Preferably shorter!

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You seem to be confusing "shorter" with "elegant" and "efficient".

    I can guarantee that if you do find a 1-line short answer, it will neither be elegant or efficient.

    Laserlight's post #10 is perfectly clear as to what is going on.

    Your post #7 is a dog's breakfast by comparison.
    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.

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    122
    But I was no longer referring to #7. I was referring to #1 and to ways which might render it not necessarily clearer, but more sophisticated. Perhaps coming up with a better algorithm altogether. Can you think of any way to achieve that?

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I am not aware of a better algorithm. If you want more "sophisticated", you could eliminate the recursion and so allow it to handle the case where a large binary tree degenerates into a linked list, hence the recursion will reach the limit.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. string to actual hex value conversion
    By Lens-art in forum C Programming
    Replies: 5
    Last Post: 03-19-2012, 02:24 AM
  2. stdio.h - where is actual code
    By voltson4 in forum C Programming
    Replies: 0
    Last Post: 02-26-2003, 05:11 PM
  3. C++ in Depth or Java In Depth... ?
    By jawwadalam in forum C++ Programming
    Replies: 8
    Last Post: 10-07-2002, 08:38 AM
  4. Actual Numbers
    By Cosmic Diva in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 06-14-2002, 09:29 PM
  5. too few actual parametrs
    By grunt161 in forum C Programming
    Replies: 3
    Last Post: 02-23-2002, 04:38 PM