Easy

Minimum Depth of Binary Tree

020

Given a binary tree encoded as level-order with -100000 as null, return its minimum root-to-leaf depth.

EXAMPLES

Example 1

Input
{
  "root": [
    3,
    9,
    20,
    -100000,
    -100000,
    15,
    7
  ]
}

Output
2

FUNCTION SHAPE

root: intArray→int

SOLUTION NOTE

Notice the difference from maxDepth - we handle empty subtrees specially. Without this, min(x, 0) would always be 0 instead of x. Compare with max(x, 0) = x.

Reveal reference solution +

pythonREFERENCE

def minDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left:
        return 1 + self.minDepth(root.right)
    if not root.right:
        return 1 + self.minDepth(root.left)
    return 1 + min(self.minDepth(root.left),
                   self.minDepth(root.right))

# Alternative with inf trick
def minDepth(self, root: Optional[TreeNode]) -> int:
    def helper(root):
        if not root: return float('inf')
        if not root.left and not root.right: return 1
        return 1 + min(helper(root.left), helper(root.right))
    return helper(root) if root else 0

TimeO(n)

SpaceO(h)

Open on LeetCode ↗