Minimum Depth of Binary Tree

Problem Statement:

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, 10<sup>5</sup>].
-1000 <= Node.val <= 1000

Optimal Solution:

# 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 and root.right is None:
            return 1
        if root.left is None:
            return self.minDepth(root.right) + 1
        if root.right is None:
            return self.minDepth(root.left) + 1

        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        return min(left_depth, right_depth) + 1

Explanation:

To find the minimum depth of a binary tree, we can use a depth-first search (DFS) algorithm. Here's the approach to solve this problem:

If the root node is None, the tree is empty, so the minimum depth is 0. Return 0.
If both the left and right child of the root are None, it means the root is a leaf node, so the minimum depth is 1. Return 1.
If the left child is None, recursively find the minimum depth of the right subtree by calling the function on the right child. Add 1 to the result and return it.
If the right child is None, recursively find the minimum depth of the left subtree by calling the function on the left child. Add 1 to the result and return it.
If both the left and right child exist, recursively find the minimum depth of both subtrees. Take the minimum of the two depths and add 1 to the result. Return the minimum depth.

Conclusion:

Hope this article will help you to find out the minimum depth of a binary tree

Happy Coding ✨

DSA Blog