Problem 44 - Minimum Depth of Binary Tree

Explore our archive for previous posts.

Problem 43 - Maximum Depth of Binary Tree

Problem 42 - First Bad Version

Problem 41 - Add Binary

Question

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, 10^5].

• -1000 <= Node.val <= 1000

Approach

This problem requires finding the minimum depth, i.e., the shortest path from the root to any leaf in a binary tree. Here's a high-level approach:

1. Base Case: If the root is null, the depth is 0.

2. Special Case: If either the left or right child is null, return the non-null child's depth plus 1.

3. Recursive Case: Calculate the depth of the left and right subtrees recursively.

4. Return Minimum: Return the minimum depth of the left and right subtrees plus 1 (for the current level).

Solution

Solve it here

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int minDepth(TreeNode root) {
        // Base case: if the root is null, the depth is 0
        if (root == null) {
            return 0;
        }
        
        // Special case: if either left or right child is null, return the non-null child's depth + 1
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        
        // Recursive case: calculate the depth of left and right subtrees
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        
        // Return the minimum depth of left and right subtrees plus 1 for the current level
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

Time and space complexity

Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once.

Space Complexity: The space complexity is O(h), where h is the height of the binary tree. In the worst case, the space required is the height of the tree, which is equivalent to the maximum depth of the recursion stack.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?