Minimum Depth of Binary Tree.md

Definitions

• This problem defines a 1-TreeNode tree to have a depth of 1.
• "minimum depth" is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node.
  • this is a strange definition. Notice it's not the shortest path to a null node, it's the shortest path to a leaf node. In an interview, it's important to verify the exact definition of "minimum depth" before proceeding.

Examples

The trees below both have a "minimum depth" of 2.

      3              1
     / \              \
    9  20              2
      /  \
     15   7

Algorithm

This problem is similar to LeetCode #104 - Maximum Depth of Binary Tree. The solution to that problem uses Depth-First Search (DFS). However, in the problem below we want to find minDepth(), so Breadth-First Search (BFS) will be a faster than DFS since it may not need to traverse every node. Implementing BFS on a tree is similar to doing a level-order traversal on a tree!

Provided Code

class TreeNode {
    TreeNode left;
    TreeNode right;
}

Solution

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new ArrayDeque(); // use deque as a queue
        deque.add(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            depth++;
            int numNodesInLevel = deque.size();
            while (numNodesInLevel-- > 0) {
                TreeNode n = deque.remove();
                if (n.left == null && n.right == null) {
                    return depth;
                }
                if (n.left != null) {
                    deque.add(n.left);
                }
                if (n.right != null) {
                    deque.add(n.right);
                }
            }
        }
        return depth; // code will never reach here
    }
}

Time/Space Complexity

Let d be the "minimum depth" of the tree.

• Time Complexity: O(2^d)
• Space Complexity: O(2^d)

O(2^d) is faster than O(n) when the tree has some branches that are shorter than others, and we don't visit every node. If the tree is perfectly balanced, then the time/space complexity is O(2^d) = O(n).

Links

• github.com/RodneyShag