{x}
blog image

Minimum Depth of Binary Tree

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

Solution Explanation for Minimum Depth of Binary Tree

The problem asks to find the minimum depth of a binary tree. The minimum depth is the shortest distance from the root node to any leaf node. A leaf node is a node with no children.

We can solve this problem using two primary approaches: Depth-First Search (DFS) and Breadth-First Search (BFS).

Approach 1: Depth-First Search (Recursion)

This approach uses recursion to traverse the tree. The core idea is:

  1. Base Case: If the current node is null, the depth is 0.
  2. Leaf Node: If the current node is a leaf node (both left and right children are null), the depth is 1.
  3. Non-Leaf Node: If the current node has at least one child, recursively calculate the minimum depth of the left and right subtrees. The minimum depth of the current node is 1 plus the minimum depth of the shallower subtree.

Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit every node. Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N.

Approach 2: Breadth-First Search (Iteration)

This approach uses a queue to perform a level-order traversal.

  1. Initialization: Add the root node to the queue and initialize the depth to 0.
  2. Iteration: While the queue is not empty:
    • Increment the depth.
    • Process all nodes at the current level. For each node:
      • If it's a leaf node, return the current depth.
      • Otherwise, add its children to the queue.

Time Complexity: O(N), where N is the number of nodes. We visit each node once. Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be proportional to N.

Code Examples

The provided code snippets demonstrate both approaches in several programming languages. The structure is consistent across all languages:

  • Function Definition: A function (e.g., minDepth) takes the root node of the binary tree as input.
  • Base Case Handling: Checks if the root is null (or equivalent in the language), returning 0 if it is.
  • Recursive DFS (Approach 1): Recursively calculates the minimum depth based on the logic explained above.
  • Iterative BFS (Approach 2): Uses a queue (deque in Python, ArrayDeque in Java, queue in C++, etc.) to perform the level-order traversal.

Note: The code examples use a standard TreeNode definition specific to LeetCode's structure. You may need to adapt this definition depending on your environment. The core logic remains the same. The choice between DFS and BFS depends on factors like memory constraints (BFS is often better for very wide trees) and coding style preference. In this particular problem, the performance difference is usually negligible unless dealing with extremely large trees.