Skip to content

111. Minimum Depth Of Binary Tree

Tree Depth-First Search Breadth-First Search Binary Tree

Problem - Minimum Depth Of Binary Tree

Easy

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.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

 

Constraints:

  • The number of nodes in the tree is in the range [0, 105].
  • -1000 <= Node.val <= 1000

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # if root is None:
        #     return 0
        # if root.left is None:
        #     return self.minDepth(root.right) + 1
        # if root.right is None:
        #     return self.minDepth(root.left) + 1

        # return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

        if root is None:
            return 0

        queue = deque()
        queue.append((root, 1))
        while len(queue) > 0:
            node, depth = queue.popleft()
            if node.left is None and node.right is None:
                return depth

            if node.left is not None:
                queue.append((node.left, depth + 1))

            if node.right is not None:
                queue.append((node.right, depth + 1))

Submission Stats:

  • Runtime: 3 ms (79.15%)
  • Memory: 50.3 MB (47.14%)