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!

• Bill Lynch: Why are you not adding 1 to the recursive call in all of the cases?
• trincot: 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.

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

• lisz1012: Just changed the solution to a python version
• Silvia: Omg of course! thank you so much. Let me know if you have a better solution for the problem :)