Minimum Depth of Binary Tree

Problem

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.

Examples

Example 1:

graph TD;
	3 --- 9 & 20;
	20 --- 15 & 7;
  
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

Solution

Method 1 - Recursion

Code

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

Method 2 - Level Order Traversal

Code

Java
public class Solution {

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

		Queue<TreeNode> nodes = new LinkedList<TreeNode>();
		Queueu<Integer> counts = new LinkedList<Integer>();

		nodes.add(root);
		counts.add(1);

		while (!nodes.isEmpty()) {
			TreeNode curr = nodes.remove();
			int count = counts.remove();

			if (curr.left == null && curr.right == null) {
				return count;
			}

			if (curr.left != null) {
				nodes.add(curr.left);
				counts.add(count + 1);
			}

			if (curr.right != null) {
				nodes.add(curr.right);
				counts.add(count + 1);
			}
		}

		return 0;
	}
}