/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
 //new solution write at 3/5/2014
public class Solution {
    public int minDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        
        if (root.left==null && root.right==null){
            return 1;
        }
        
        if (root.left!=null && root.right!=null){
            return 1+Math.min(minDepth(root.left), minDepth(root.right));
        }
        
        if (root.left==null){
            return 1+minDepth(root.right);
        }
        
       
        return 1+minDepth(root.left);
        
        
    }
    
}



"Be care of that is the current root is empty the already added depth should -1 and return "

"Time Complexity is O(n)"

public class Solution {
    public int minDepth(TreeNode root) {
        
        if (root == null){
            return 0;
        }
        else if (root.left==null && root.right==null){
            return 1;
        }
        
        return minDepthHelper(root, 1);
        
     }
     public int minDepthHelper(TreeNode root, int depth){
         if (root==null){
             // if the current root is null, then the depth should -1 and return;
             return depth-1;
         }
         
         int left=minDepthHelper(root.left, depth+1);
         int right=minDepthHelper(root.right, depth+1);
         // if left ==depth mean the left node is null, so return the right
         if (left==depth){
             return right;
         }
         // if rigth==depth mean the right node is null, so return left
         if (right==depth){
             return left;
         }
         
         return Math.min(left,right);
         
     }
}