---
tags: data_structure_python
---

# Minimum Depth of Binary Tree <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

<ins>**Example:**</ins>

Given binary tree ```[3,9,20,null,null,15,7]```,

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

## Solution

### Solution 1: Depth First Search

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

class Solution:
    # DFS
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        elif root.left is None and root.right is None:
            return 1
        else:
            l = self.minDepth(root.left)
            r = self.minDepth(root.right)
            
            if root.right is None:
                return 1 + l
            if root.left is None:
                return 1 + r
            
            return 1 + min(l, r)

### Solution 2: Breadth First Search

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

class Solution:

    def minDepth(self, root: TreeNode) -> int:
        # BFS
        if root is None:
            return 0
        else:
            h = 1
            queue = [root, None]
            
            while len(queue) > 0:
                node = queue.pop(0)
                
                if node is None:
                    if len(queue) > 0: # Level marker
                        h += 1
                        queue.append(None)
                else:
                    if node.left is None and node.right is None:
                        return h 
                    if node.left is not None:
                        queue.append(node.left)
                    if node.right is not None:
                        queue.append(node.right)
            return h