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.

**Thoughts:**

Sense of recursion should be came out now.

What is the base case or edge case? Empty tree. What is the minimum depth of an empty tree? 0.

In the recursion step, the passed in TreeNode “root” is been looked at. “root” is not null, which was covered in the base case. Then there are four sub-cases or combinations, if you like:

- root is a leaf node. In other word, root.left == null && root.right == null. Return 1 at this case.
- root.left == null && root.right != null. Then we just need to recurse on the right, so we return 1 + minDepth(root.right).
- root.left != null && root.right == null. Similarly, we return 1 + minDepth(root.left).
- root.left != null && root.right != null. This is rather interesting case. We don’t know which branch of the case has shorter path, so we should return the minimum of these two.

In the code, we can actually combine the four cases into two!

**Code (Java):**

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

**Code (C++):**

class Solution {
public:
int minDepth(TreeNode *root) {
if(root == NULL)
return 0;
else if(root -> left != NULL && root -> right != NULL)
return 1 + min(minDepth(root -> left), minDepth(root -> right));
else
return 1 + minDepth(root -> right) + minDepth(root -> left);
}
};

### Like this:

Like Loading...

*Related*

wycinka drzew filmy bochnia

May 28, 2014@ 09:44:43Very well written article. It will be supportive to everyone who utilizes it, as well as myself.

Keep doing what you are doing – for sure i will check

out more posts.