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, 10^5].
• -1000 <= Node.val <= 1000

Try this Problem on your own or check similar problems:

1. Average of Levels in Binary Tree
2. Maximum Depth of Binary Tree
3. Binary Tree Level Order Traversal

Solution:

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int level = 1;

    while(!q.isEmpty()){
        int size = q.size();
        while(size-- > 0) {
            TreeNode node = q.poll();
            if(node.left == null && node.right == null){
                return level;
            }
            if(node.left != null){
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
        }
        ++level;
    }
    return level;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

Explanation:

We do a BFS search just like in Average of Levels in Binary Tree , only this time we’re keeping track of what level we’re currently at and terminate as soon as we find first leaf node (both left and right child is null). Notice that DFS (depth first search) is not the best choice since we’re looking for the shortest tree path, in other words imagine a left tree with 10000 nodes contained in the path to the left most tree node, and imagine right leaf node path containing only 1 element. We would spend too much time on the left subtree just to return depth of 2 when we search in right subtree.