# LeetCode 111: Minimum Depth of Binary Tree ## Problem Restatement We are given the `root` of a binary tree. We need to return 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. A leaf is a node with no children. For this tree: ```text 3 / \ 9 20 / \ 15 7 ``` The nearest leaf is `9`. The path is: ```text 3 -> 9 ``` This path contains `2` nodes, so the answer is: ```python 2 ``` ## Input and Output | Item | Meaning | |---|---| | Input | `root`, the root node of a binary tree | | Output | Minimum number of nodes from root to nearest leaf | | Empty tree | Return `0` | | Leaf | A node with no left child and no right child | | Important detail | A node with one child is not a leaf | LeetCode gives the `TreeNode` class: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` The function shape is: ```python class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: ... ``` ## Examples Consider: ```text 3 / \ 9 20 / \ 15 7 ``` The root-to-leaf paths are: ```text 3 -> 9 3 -> 20 -> 15 3 -> 20 -> 7 ``` Their depths are: ```text 2 3 3 ``` The minimum depth is: ```python 2 ``` Now consider a skewed tree: ```text 2 \ 3 \ 4 \ 5 \ 6 ``` There is only one root-to-leaf path: ```text 2 -> 3 -> 4 -> 5 -> 6 ``` So the answer is: ```python 5 ``` For an empty tree: ```python root = None ``` The answer is: ```python 0 ``` ## First Thought: Use Breadth-First Search The problem asks for the shortest path from the root to a leaf. In a tree, breadth-first search visits nodes by depth: ```text depth 1 depth 2 depth 3 ... ``` So the first leaf found by BFS is the nearest leaf. That means we can stop early. We do not need to visit the whole tree if a shallow leaf appears first. ## Key Insight Use a queue that stores pairs: ```python (node, depth) ``` Start with: ```python (root, 1) ``` Then process nodes from the queue. When we remove a node from the queue: 1. If it is a leaf, return its depth. 2. Otherwise, add its children with depth `depth + 1`. Because BFS processes smaller depths before larger depths, the first leaf gives the minimum depth. ## Algorithm If `root` is `None`, return `0`. Otherwise: 1. Create a queue containing `(root, 1)`. 2. While the queue has nodes: 1. Remove the front pair `(node, depth)`. 2. If `node` has no left child and no right child, return `depth`. 3. If `node.left` exists, add `(node.left, depth + 1)`. 4. If `node.right` exists, add `(node.right, depth + 1)`. ## Correctness Breadth-first search processes nodes in increasing depth order. The queue starts with the root at depth `1`. When a node at depth `d` is processed, its children are added with depth `d + 1`. Since the queue is first-in-first-out, all nodes at depth `d` are processed before any node at depth `d + 1`. A valid minimum-depth path must end at a leaf. The algorithm returns only when it reaches a node with no children. The first leaf reached by BFS has the smallest possible depth among all leaves, because no deeper node can be processed before all shallower nodes. Therefore, returning that depth gives the minimum depth of the tree. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | In the worst case, BFS may visit every node | | Space | `O(n)` | The queue may hold many nodes from one level | Here, `n` is the number of nodes in the tree. BFS may stop early if it finds a shallow leaf. ## Implementation ```python from collections import deque from typing import Optional # 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 q = deque([(root, 1)]) while q: node, depth = q.popleft() if node.left is None and node.right is None: return depth if node.left is not None: q.append((node.left, depth + 1)) if node.right is not None: q.append((node.right, depth + 1)) return 0 ``` ## Code Explanation Handle the empty tree: ```python if root is None: return 0 ``` Initialize the queue: ```python q = deque([(root, 1)]) ``` The root has depth `1` because depth counts nodes, not edges. Process nodes in BFS order: ```python while q: node, depth = q.popleft() ``` Check whether the current node is a leaf: ```python if node.left is None and node.right is None: return depth ``` If this is the first leaf reached, BFS guarantees it has minimum depth. Add existing children: ```python if node.left is not None: q.append((node.left, depth + 1)) if node.right is not None: q.append((node.right, depth + 1)) ``` The final `return 0` is only a safety fallback. ## Testing ```python from collections import deque from typing import Optional 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 q = deque([(root, 1)]) while q: node, depth = q.popleft() if node.left is None and node.right is None: return depth if node.left is not None: q.append((node.left, depth + 1)) if node.right is not None: q.append((node.right, depth + 1)) return 0 def run_tests(): s = Solution() root1 = TreeNode( 3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)), ) assert s.minDepth(root1) == 2 root2 = TreeNode( 2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))), ) assert s.minDepth(root2) == 5 root3 = None assert s.minDepth(root3) == 0 root4 = TreeNode(1) assert s.minDepth(root4) == 1 root5 = TreeNode( 1, TreeNode(2, TreeNode(4), None), TreeNode(3), ) assert s.minDepth(root5) == 2 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `[3,9,20,null,null,15,7]` | Standard example where nearest leaf is shallow | | `[2,null,3,null,4,null,5,null,6]` | Skewed tree, only one leaf | | Empty tree | Confirms base case | | Single node | Root itself is a leaf | | Mixed tree | Confirms BFS stops at nearest leaf |