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?
@Avinash, thanks for ID'ing the edge case. And the problem @kellyBundy https://leetcode.com/problems/minimum-depth-of-binary-tree/submissions/
class Solution(object):
def minDepth(self, node):
# no node (dead branch)
if node is None:
return 0
lDepth = self.minDepth(node.left)
rDepth = self.minDepth(node.right)
if node.left and node.right:
return min(lDepth, rDepth) + 1
else: #prevents counting first dead branch as minDepth
return max(lDepth, rDepth) + 1