(Minimum Depth of Binary 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):

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);
    }
};
Advertisements

1 Comment (+add yours?)

  1. wycinka drzew filmy bochnia
    May 28, 2014 @ 09:44:43

    Very 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.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: