(Minimum Depth of Binary Tree)

(Minimum Depth of Binary Tree)

05 Mar 2013 1 Comment

by Runhe Tian in LeetCode Tags: C++, Java, Recursion, 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.

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:

1. root is a leaf node. In other word, root.left == null && root.right == null. Return 1 at this case.
2. root.left == null && root.right != null. Then we just need to recurse on the right, so we return 1 + minDepth(root.right).
3. root.left != null && root.right == null. Similarly, we return 1 + minDepth(root.left).
4. 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):

Code (C++):