pythonbinary-tree

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?


Solution

  • @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