0111.md

111. Minimum Depth of Binary Tree

Level:

Topic:

Question

Given a binary tree, find its minimum depth.

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

Intuition

Recursive:

• since we don't have control over recursive calls, find all depth and return the minimum depth.

Iterative:

• BFS with a queue, do a level order traversal and if sees the first leaf node, it's the min depth.

Code

Time: O(n)
Space: O(n)

Recursive

public int minDepth(TreeNode root) {
    if(root==null)
        return 0;
    if(root.left==null)
        return minDepth(root.right) +1;
    if(root.right==null)
        return minDepth(root.left)+1;
    return 1 + Math.min(minDepth(root.left),
                        minDepth(root.right));
}

int ans = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    helper(root, 0);
    return ans;
}

private void helper(TreeNode root, int level) {
    if (root == null)
        return;

    if (root.left == null && root.right == null)
        ans = Math.min(ans, 1+level);

    helper(root.left, level+1);
    helper(root.right, level+1);
}

Iterative

public int minDepth(TreeNode root) {
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    if(root != null)
        queue.add(root);

    while (!queue.isEmpty()) {
        int n = queue.size();
        while (n-- > 0) {
            root = queue.poll();
            if (root.left == null && root.right == null)
                return depth+1;

            if(root.left != null)
                queue.add(root.left);
            if(root.right != null)
                queue.add(root.right);
        }
        depth++;
    }

    return depth;
}