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.

Example Given a binary tree as follow:

  1
 / \ 
2   3
   / \
  4   5

The minimum depth is 2.

Solution 1: DFS. Notice that if we direct get min value it will get wrong answers, because for those tree have no left or right subtree we will get 0 with Math.min. So we need to check if has left or right subtrees.

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;
    }
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    return Math.min(left, right) + 1;
}

Solution 2: BFS.

public int minDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    int depth = 0;
    boolean isLeaf = false;
    while(!queue.isEmpty()) {
        int size = queue.size();
        depth++;
        for(int i = 0; i < size; i++) {
            TreeNode tmp = queue.poll();
            if(tmp.left == null && tmp.right == null) {
                isLeaf = true;
                break;
            }
            if(tmp.left != null) {
                queue.offer(tmp.left);
            }
            if(tmp.right != null) {
                queue.offer(tmp.right);
            }
        }
        if(isLeaf) {
            return depth;
        }
    }
    return depth;
}