Finding minimum depth of BST ... findHeight function won't work

Question

Trying to solve this LC Easy: https://leetcode.com/problems/minimum-depth-of-binary-tree/

Which is to find the minimum depth (number of nodes on shortest path) of a tree.

I was able to create a "findheight" function which gives me the height of a tree.

My logic was to use findheight to find the height of both subtrees (left and right) of a root node, and then return the minimum between the two heights.

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){return 0;}
        int left = findHeight(root.left);
        int right = findHeight(root.right);

        //unbalanced tree, only one subtree 
        if(left == 0 || right == 0){
            return Math.max(left,right) + 1;
        }
        return Math.min(left,right) + 1 ;
    }
    
    public int findHeight(TreeNode root){
        if(root == null){return 0;}
        int left = findHeight(root.left);
        int right = findHeight(root.right);
        return Math.max(left,right) + 1;
    }
}

It won't pass the test case:

[-9,-3,2,null,4,4,0,-6,null,-5]

Or:

Output:
4
Expected:
3

My thought process right now is that when I use "findHeight", I'm returning back the 'max' height per left and right subtree. In this test case, I should be returning back the minimum height.

I changed my code to "Math.min" in another iteration, but that doesn't work either.

Any ideas or theories why? So confused!! Should I just abandon this approach altogether?

Answer 1

Issue in current code

//unbalanced tree, only one subtree 
if(left == 0 || right == 0){
  return Math.max(left,right) + 1;
}

The above lines of code checks the imbalance only at root level. It does not recursively check imbalance at lower levels.

Check imbalance at every level

    public int minDepth(final TreeNode node) {
        if (node == null) {
            return 0;
        }
        final int left = minDepth(node.left);
        final int right = minDepth(node.right);
        
        // if both paths exist, then return the minimum
        if (node.left != null && node.right != null) {
            return Math.min(left, right) + 1;
        } else {
            // if zero or one path exists return that path (so take maximum)
            return Math.max(left, right) + 1;
        }
    }