Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0111 - Minimum Depth of Binary Tree
    0111 - Minimum Depth of Binary Tree
    0111 - Minimum Depth of Binary Tree
    0111 - Minimum Depth of Binary Tree

    0111 - Minimum Depth of Binary Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/minimum-depth-of-binary-tree/

    Solution 1 - Recursive DFS

    Use depth-first search to recursively find the minimum depth. The key insight is that if a node has only one child, we must follow that child (not treat the missing child as depth 0). Only when both children are None is it a leaf node.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)

    Solution 2 - BFS (Level-Order Traversal)

    Use breadth-first search to traverse the tree level by level. The first leaf node encountered is guaranteed to be at the minimum depth, so we can return immediately without exploring the rest of the tree.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0111.1 - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def minDepth(self, root: Optional[TreeNode]) -> int:
        """Minimum Depth of Binary Tree Function"""
        if not root:
            return 0

        # If only right child exists, recurse right
        if not root.left:
            return 1 + self.minDepth(root.right)

        # If only left child exists, recurse left
        if not root.right:
            return 1 + self.minDepth(root.left)

        # Both children exist, take the minimum
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: [3,9,20,null,null,15,7] -> 2
    root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(Solution().minDepth(root1))

    # Example 2: [2,null,3,null,4,null,5,null,6] -> 5
    root2 = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))
    print(Solution().minDepth(root2))

    # Edge case: empty tree -> 0
    print(Solution().minDepth(None))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0111.2 - Solution 2 - BFS Level-Order Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def minDepth(self, root: Optional[TreeNode]) -> int:
        """Minimum Depth of Binary Tree Function"""
        if not root:
            return 0

        queue = deque([(root, 1)])

        while queue:
            node, depth = queue.popleft()

            # First leaf node found is at minimum depth
            if not node.left and not node.right:
                return depth

            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))

        return 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: [3,9,20,null,null,15,7] -> 2
    root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(Solution().minDepth(root1))

    # Example 2: [2,null,3,null,4,null,5,null,6] -> 5
    root2 = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))
    print(Solution().minDepth(root2))

    # Edge case: empty tree -> 0
    print(Solution().minDepth(None))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()