Help about "Minimum Depth of Binary Tree" problem solution

  • 1

    I used recursive method to compute each node's depth. Here is my code:

    public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        int i = getMinDepth(root.left);
        int j = getMinDepth(root.right);
        if(i == 0 || j == 0)
            return 1+i+j;
        return Math.min(i,j) + 1;
    private int getMinDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;


    this code can not pass the input {1,2,3,4,#,#,5}. Expected is 3, but my output is 2.

    And also I can not know the input {1,2,3,4,#,#,5} is inorder Traversal or postorder or preorder.

  • 6

    {1,2,3,4,#,#,5} is a modified level-order traversal. It is defined in, as well as in a few other places, but is basically a level-order traversal where #means the line of descent ends, so no more entries come from it.

    This tree looks like this:

      2   3
    4       5

    Your algorithm currently finds the minimum depth of a null, not the minimum leaf. You account for the possibility of a null in minDepth(), but not in getMinDepth(), so it advances to 2-3 layer and the switches to getMinDepth, returning 1 for the depth of 2-3.

               return min(0,1)+1 = 1
         return min...+1 = 2

    In order to fix this, change this:

    int i = getMinDepth(root.left);
    int j = getMinDepth(root.right);

    To this:

    int i = minDepth(root.left);
    int j = minDepth(root.right);

    You can get rid of getMinDepth().

  • 0

    Thank you for the explanation. Help me a lot :)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.