Problem with Minimum Depth of Binary Tree

Question

Can someone help me figure out what's wrong with my code?

This test case doesn't work - [2,null,3,null,4,null,5,null,6] - my code returns 0 instead of 5. Not sure why.

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root.left is None and root.right is None:
            return 0
        elif root.left is None and root.right is not None:
            return self.minDepth(root.right)
        elif root.right is None and root.left is not None:
            return self.minDepth(root.left)
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

Thank you!

Why are you not adding 1 to the recursive call in all of the cases? — Bill Lynch
– Bill Lynch, Commented May 8, 2021 at 17:42
This would be so easy to solve if you would just debug and step through the code, and look at the values that variables have an function calls return. Once you do that, you'll find no reason to post this question. — trincot
– trincot, Commented May 8, 2021 at 17:52

lisz1012 · Accepted Answer · 2021-05-08 18:07:01Z

1

You should check the root it self first, in case the input is an empty tree (root is None). You will get an NPE without this null check. And you need to include the current root itself in the elif block as well. This is my accepted code:

class Solution(object):
    def minDepth(self, root):
        if root is None:
            return 0
        elif root.left is None and root.right is not None:
            return self.minDepth(root.right) + 1
        elif root.right is None and root.left is not None:
            return self.minDepth(root.left) + 1
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

edited May 8, 2021 at 18:07

answered May 8, 2021 at 17:54

lisz1012

213 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

lisz1012 Over a year ago

Just changed the solution to a python version

Silvia Over a year ago

Omg of course! thank you so much. Let me know if you have a better solution for the problem :)

Collectives™ on Stack Overflow

Problem with Minimum Depth of Binary Tree

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related