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.

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

---

But that returns maxdepth + 1, and not the actual maxdepth.

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.

depth 0. I have tried your code and it gave 7 where it supposed to have given 6 (and whereas my code gave 6).

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

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

---

I think it pointlessly calls findMaxDepth() more times than necessary.

I could have used more variables, agreed. But how may I improve the function I opened this thread with?

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

---

But other than that, can you come up with a more elegant/sophisticated code to yield the same output?
Preferably shorter!

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.

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?

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.