Minimum depth of a binary tree

Question

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
Copy

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
Copy

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

Answer 1

I think its because of the min function. Starting from 2, your code checks the left which is 0, then checks right which is recursively checked and returns 4. However, you call min(0, 4)+1 which gives you an output of 1.

Answer 2

Your code stops recursion on None which is not a TreeNode, obviously, the term "depth" is undefined for such objects. Try to stop your recursion on so-called "leafs": nodes without children. Check out my solution for this problem:

def is_leaf(node: TreeNode):
    return node.left is None and node.right is None

def min_depth(root: TreeNode):
    if is_leaf(root):
        return 1
    not_none_children = (
        child if child is not None
        for child in (root.left, root.right)]
    )
    return min(min_depth(child) for child in not_none_children) + 1
Copy

Answer 3

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