Why is my maximum depth solution for binary tree returning one less than it is supposed to?

Question

I am solving the following Leetcode problem: https://leetcode.com/problems/maximum-depth-of-binary-tree/solution/

It is to return the maximum depth of a binary tree.

Here is my solution:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        
        if not root:
            return 0

        stack = [(root, 1)]
        
        curr_depth = 1
        while stack:
            node, depth = stack.pop()
            depth = max(curr_depth,depth)
            if node.right:
                stack.append((node.right, curr_depth + 1))
            if node.left:
                stack.append((node.left, curr_depth + 1))
        
        return depth

For some reason the output is always one less than it is supposed to be. And looking at the accepted solutions, they look very similar to mine, but I can't seem to find where my solution is going wrong.

Was `node, depth = stack.pop()` supposed to say `node, curr_depth`? — user2357112, Jul 18 '21 at 09:55
@mkrieger1 - the debugger showed no errors. I am running it on Pycharm — Patrick Chong, Jul 18 '21 at 10:00
A debugger is not to find errors (the Python interpreter will already tell you if there is an error), but to find bugs, i.e. wrong behaviour of the program by your mistake; see [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/), and [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — mkrieger1, Jul 18 '21 at 10:02
Thanks for the links mkrieger1, I will read through them- very useful! — Patrick Chong, Jul 18 '21 at 10:04

score 0 · Accepted Answer · answered Jul 18 '21 at 10:07

Does this help?

from typing import Optional

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self._visit(root, 0)
    
    def _visit(self, node: Optional[TreeNode], depth: int) -> int:
        if not node:
            return depth
        return max(self._visit(node.left, depth + 1), self._visit(node.right, depth + 1))

score 0 · Answer 2 · answered Jul 25 '21 at 19:52

So your offending variables are depth and curr_depth. Basically when depth = max(curr_depth,depth) occurs, you want to assign this to curr_depth. Then in adding to the stack you want to pass depth+1 not curr_depth+1, finally you want to return curr_depth and not depth. curr_depth represents the current maximum depth while depth is a temporary variable representing the depth of the node in consideration. Its best to be consistent.

I won't waste your time and copy and paste an efficient algorithm that is correct, as you said your question is regarding why your algorithm is failing, as you already have seen many working implementations.

Why is my maximum depth solution for binary tree returning one less than it is supposed to?

2 Answers2