[LeetCode] #111: Minimum Depth of Binary Tree

Problem:

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.

---

Process:

Objective: Find the minimum depth of a given tree

Constraints:
1. The number of nodes in the tree is in the range [0, 10^5].
2. -1000 <= Node.val <= 1000

Additional Details:

---

Solution:

Approach #1: (Iteration) DFS to find the minimum depth

• Time Complexity: O(n) where n is the number of TreeNode
• Space Complexity: O(n)

How it Works:
1. DFS through the nodes while keeping track of the minimum depth
2. Compare the depth of each leaf and update the minimum depth

def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        node_tuple = (root, 1)
        min_depth = None
        stack = []
        
        while node_tuple:
            node, cur_depth = node_tuple
            # Check if current_node is a leaf
            if not node.left and not node.right:
                if not min_depth or min_depth > cur_depth:
                    min_depth = cur_depth
                    
            if node.right:
                stack.append((node.right, cur_depth+1))
            if node.left:
                stack.append((node.left, cur_depth+1))
            
            if stack:
                node_tuple = stack.pop()
            else:
                node_tuple = None
        
        return min_depth

Slightly Faster Version:

def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        node_tuple = (root, 1)
        min_depth = float('inf')
        nodes_to_visit = []
        
        while node_tuple:
            node, cur_depth = node_tuple
            # Check if current_node is a leaf
            if not node.left and not node.right:
                min_depth = cur_depth
                    
            if node.right and min_depth > cur_depth:
                nodes_to_visit.append((node.right, cur_depth+1))
            if node.left and min_depth > cur_depth:
                nodes_to_visit.append((node.left, cur_depth+1))
            
            if nodes_to_visit:
                node_tuple = nodes_to_visit.pop()
            else:
                node_tuple = None
        
        return min_depth

Approach #2: (Recursion) DFS to find the minimum depth

• Time Complexity: O(n) where n is the number of TreeNode
• Space Complexity: O(n)

How it Works:
Same as above.

def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        if root.left and root.right:
            return min(self.minDepth(root.left)+1, self.minDepth(root.right)+1)
        elif root.right:
            return self.minDepth(root.right)+1
        elif root.left:
            return self.minDepth(root.left)+1
        else:
            return 1

Simpler but takes longer time

def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        if root.left and root.right:
            return min(self.minDepth(root.left)+1, self.minDepth(root.right)+1)
        else:
            return max(self.minDepth(root.left)+1, self.minDepth(root.right)+1)

---

LeetCode Question #111