[Python] Minimum depth of a binary tree

I'm trying to write code to find the minimum depth of a binary tree. https://leetcode.com/problems/minimum-depth-of-binary-tree/

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):

def minDepth(self, node):
if node is None:
return 0

else :
# Compute the depth of each subtree
lDepth = self.minDepth(node.left)
rDepth = self.minDepth(node.right)
return min(lDepth, rDepth) + 1


However, this solution does not work on some test cases, such as a highly unbalanced binary tree, which devolves to a linked list (ex [2, None, 3, None, 4, None, 5, None, 6]

The minimum depth is 5 (as None children do not count.) However, my solution returns 1, so it must be treating the left child of 2 as the minimum depth leaf node.

2
/ \
3
/ \
4
/ \
5
/ \
6


I'm at a loss, why does this solution not adequately address this use case?

Continue reading...