#111

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Minimum Depth of Binary Tree

Find the minimum depth of a binary tree, which is the shortest path from the root node to the nearest leaf node.

tree depth first search breadth first search binary tree

Problem Statement

You are given a binary tree, and your task is to find the minimum depth. The minimum depth is defined as the number of nodes along the shortest path from the root to the nearest leaf node. A leaf node is one with no children, and the depth is measured from the root to any such leaf.

In some cases, the binary tree may not have all child nodes. It's important to understand that if the tree is unbalanced, the shortest path might involve nodes that are only partially filled with children. Therefore, special care is required to ensure the minimum depth is calculated correctly, even in skewed or sparse trees.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: 2

Example details omitted.

Example 2

Input: root = [2,null,3,null,4,null,5,null,6]

Output: 5

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 105].
-1000 <= Node.val <= 1000

Solution Approach

BFS Traversal

Using a breadth-first search (BFS) is an efficient way to find the minimum depth of a binary tree. In BFS, nodes are processed level by level, and the first leaf node encountered will guarantee the shortest depth. As BFS explores the tree, track the depth of each node until a leaf node is found.

DFS Traversal with Early Exit

A depth-first search (DFS) can also be used, but it requires tracking the depth at each node. To avoid unnecessary deep traversal, early exit can be employed when a leaf is found. This ensures that once a leaf node is encountered, the search doesn't go deeper than necessary.

State Tracking during Traversal

Effective state tracking is crucial for both BFS and DFS. In BFS, maintain a queue with both the node and its current depth. For DFS, pass the current depth as you recursively explore the tree. Make sure that state is updated correctly to prevent incorrect depth calculations, especially when trees are unbalanced.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N) where N is the number of nodes in the tree, as each node needs to be visited. The space complexity is O(N) for the queue or recursion stack, depending on the approach used, as the entire tree may be stored temporarily during traversal.

What Interviewers Usually Probe

Do you understand the difference between BFS and DFS for this problem?
Can you explain how early exit can improve the DFS approach?
Will you consider edge cases such as an empty tree or trees with only one branch?

Common Pitfalls or Variants

Common pitfalls

Not considering edge cases like empty trees or a single-node tree.
Forgetting to handle unbalanced trees where one side is deeper than the other.
Misunderstanding the depth of the tree, confusing the total number of nodes with the path to a leaf node.

Follow-up variants

Find the maximum depth of a binary tree using the same traversal methods.
Solve for the depth of a binary tree where each node has only one child.
Determine the depth of a binary search tree and compare it with its balanced version.

FAQ

What is the minimum depth of a binary tree?

The minimum depth is the shortest path from the root node to the nearest leaf node, measured in terms of the number of nodes.

How can BFS be applied to solve the Minimum Depth of Binary Tree?

BFS is used to traverse the tree level by level. The first leaf node encountered will provide the minimum depth.

What are the time and space complexities for the solution?

Both BFS and DFS solutions have a time complexity of O(N), where N is the number of nodes. The space complexity is O(N) due to the need to store nodes during traversal.

How does DFS handle unbalanced trees in finding the minimum depth?

DFS can handle unbalanced trees by exploring one branch completely before backtracking. Early exit helps avoid unnecessary deep traversal when a leaf node is found.

What edge cases should be considered when solving this problem?

Edge cases include an empty tree, a tree with a single node, and trees with unbalanced depths where one branch is significantly deeper than the other.

terminal

Solution

Solution 1: Recursion

The termination condition for recursion is when the current node is null, at which point return $0$. If one of the left or right subtrees of the current node is null, return the minimum depth of the non-null subtree plus $1$. If neither the left nor right subtree of the current node is null, return the smaller value of the minimum depths of the left and right subtrees plus $1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Solution 2: BFS

Use a queue to implement breadth-first search, initially adding the root node to the queue. Each time, take a node from the queue. If this node is a leaf node, directly return the current depth. If this node is not a leaf node, add all non-null child nodes of this node to the queue. Continue to search the next layer of nodes until a leaf node is found.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#112 path sum #116 populating next right pointers in each node #117 populating next right pointers in each node ii