LeetCode 111. Minimum Depth of Binary Tree

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        TreeNode rightMost = root;
        q.add(root);
        int depth = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) {
                break;
            }
            if (node.left != null) {
                q.add(node.left);
            }
            if (node.right != null) {
                q.add(node.right);
            }
            if (node == rightMost) {
                depth++;
                rightMost = (node.right != null) ? node.right : node.left;
            }
        }

        return depth;
    }
}

We use BFS to solve this problem. We add nodes at the same level to a queue q. We iterate through each of the nodes. When we encounter a leaf node, we stop and return depth (the minimum depth). After iterating all the nodes at the same level, we still cannot find a leaf node, we increment depth by 1 then repeat the above process for the nodes at the next level. We can use DFS as well. However, BFS outperforms DFS on highly unbalanced trees since it terminates once it reaches the first leaf node.

Time Complexity: O(n)

Extra Space: O(1)