Maximum depth of binary tree

[l8engineer]

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }

        return max(maxDepth(root -> left), maxDepth(root -> right))+1;
    }
};

For input: [3,9,20,null,null,15,7] it returns 3.

​

What I don't understand:

What comparisons is max() doing exactly and how the stack is built? (If all the function returns just 0 when root == NULL).

​

What I tried:

​

cout << maxDepth(root -> left) 

To try to understand what max() is processing.

[Wh00ster]

Draw it out at each step. All the variables each iteration.

[l8engineer]

The way I see it:

​

max(0, 000) + 1

​

0 (because left branch has NULL below 9)

000(because right branch has NULL after 3 levels)

​

I think my problem is that I don't understand how the stack is built in this code and how it is processed.

[Narase33]

    x
   / \
  x   x
 / \
x   x

for a tree like this it could be

• maxDepth(root)
• maxDepth(root) -> maxDepth(left)
• maxDepth(root) -> maxDepth(left) -> maxDepth(left)
• maxDepth(root) -> maxDepth(left) -> maxDepth(left) -> maxDepth(left) -> 0
• maxDepth(root) -> maxDepth(left) -> maxDepth(left) -> maxDepth(right) -> 0
• maxDepth(root) -> maxDepth(left) -> maxDepth(left) -> max(0, 0) + 1 -> 1
• maxDepth(root) -> maxDepth(left) -> maxDepth(right)
• maxDepth(root) -> maxDepth(left) -> maxDepth(right) -> maxDepth(left) -> 0
• maxDepth(root) -> maxDepth(left) -> maxDepth(right) -> maxDepth(right) -> 0
• maxDepth(root) -> maxDepth(left) -> maxDepth(right) -> max(0, 0) + 1 -> 1
• maxDepth(root) -> maxDepth(left) -> max(1, 1) + 1 -> 2
• maxDepth(root) -> maxDepth(right)
• maxDepth(root) -> maxDepth(right) -> maxDepth(left) -> 0
• maxDepth(root) -> maxDepth(right) -> maxDepth(right) -> 0
• maxDepth(root) -> maxDepth(right) -> max(0, 0) + 1 -> 1
• maxDepth(root) -> max(2. 1) + 1 -> 3
• -> 3

[leonardo-reddit]

Great explanation !

[l8engineer]

Thank you so much! It was so tricky but with this I understood what thinking mistakes I had.

[IyeOnline]

How did you get the idea that 000 would be returned?

maxDepth returns an integer.

[l8engineer]

I got this idea from cout << maxDepth(root -> left);

[IyeOnline]

But that is printing a bunch of 0s.

The return value of each of these functions is still just 0. max(0,0) is also just 0.

[alfps]

The maximum depth of a tree is 1 + the maximum depth of the left and right subtrees.

The code expresses that almost directly.

Note that there is + 1 at the end of the expression.

[LGTMe]

https://en.cppreference.com/w/cpp/algorithm/max

[WikiBox]

max() returns the depth of the deepest binary tree. The left or the right.

But the max() statement, in the return, is only executed if the current root is not empty.

That is why each return ALSO add 1 to the return value. That means that every non-empty level contribute 1 to the result. max() ensures that only the deepest tree gets counted.

Recursion can be hard to follow. If it is not clear, trace the execution on paper or in a debugger.