[Leetcode] Minimum Depth of Binary Tree

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

Analysis:
A pretty simple question, isn't ? Not really, if you come up with below solution (lots of online sources did), it's incorrect.

Solution 1:
    int min(int a, int b)
    {
        return (a <  b) ? a : b;
    }
 
    int minDepth(TreeNode *root) {
     
        if(root == NULL)
          return 0;
       
        int left = minDepth(root->left);
        int right = minDepth(root->right);
 
        return 1 + min(left, right);
     
    }

What is missing above is when root->left is NULL (or root->right is NULL), your min depth always returns 1 instead of calculating real minimum depth.  Correct way is to add this sanity checks.

Solution 2:
    int min(int a, int b)
    {
        return (a <  b) ? a : b;
    }
 
    int minDepth(TreeNode *root) {
     
        if(root == NULL)
          return 0;
       
        int left = minDepth(root->left);
        int right = minDepth(root->right);
     
        if(left == 0)
            return 1 + right;
 
        if(right == 0)
            return 1 + left;
         
        return 1 + min(left, right);
     
    }

Final thoughts:
I been thinking solution 1 is correct for years until very recently.  The sanity check is not needed for maxDepth but minDepth.