minimum height of a binary tree?

Question

I am asking this question after reading the below post:

How to find minimum possible height of tree?

Actually I want my algorithm to return 4 if the input given to a binary tree is as follows: 100, 50, 70, 60.

but the below code returns only 1 because it does not distinguish between a leaf[left == NULL && right == NULL] and a node with only one child.

int minDepth(TreeNode root)  {
    if (root == null) { 
        return 0;
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

No one has explained what should we do if we want the output as 4 instead of 1.

Can anyone please show me the code which returns 4 instead of 1 ?

I think I have chosen the wrong sample values above and people are getting confused about what am I actually looking for !! So, re-framing my questions below:

Assume that any node can have 0,1, or 2 children. Please consider this sample input - 100, 50, 150, 30, 70, 200, 20, 40, 60, 80, 10. Now I want my function to return the height as 3 [100->150->200]. I am calling this branch [100->150->200] as the minimum height of the tree. I may be wrong in the analogy of minimum height BUT all I want is to return 3.

The tree looks like this -

                        100
                      /     \\
                     /       \\
                  50          150
                 /   \           \\
              30       70         200
              / \     /  \
            20  40   60  80
           /
          10

And I need to find out the shortest distance between root node and the leaf node [100->150->200] =3.

This is my code -

struct node
{
    struct node* left;
    int data;
    struct node* right;
};

void add(struct node** root, int data)
{
    if(*root == NULL)
    {
        (*root) = (struct node*)malloc(sizeof(node));
        (*root)->left = NULL;
        (*root)->right = NULL;
        (*root)->data = data; 
    }
    else
    {
        if(data < (*root)->data )
            add(&(*root)->left, data);
        else
            add(&(*root)->right, data);
    }

}

void inorder(struct node* root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int minDepth(struct node* root)  
{
    if (root == NULL) 
    { 
        return 0;
    }
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

int main()
{
        struct node* root = NULL;
        add(&root, 100);
        add(&root, 50);
        add(&root, 150);
        add(&root, 30);
        add(&root, 70);
        add(&root, 200);
        add(&root, 20);
        add(&root, 40);
        add(&root, 60);
        add(&root, 80);
        add(&root, 10);
        inorder(root);
        cout<<endl;
        int i = minDepth(root);
        cout<<i<<endl; // this should be 3
        getchar();
        return 0;
}

Answer 1

It seems to me that you want to know the size of the tree and not it's height.

So instead of choosing the smallest height of the two subtrees below your root (the minDepth function) you want to sum their sizes.

The following function adds one to the size of each of left and right subtrees if the node is not null (wouldn't really be a node at all and should not be counted).

int sizeOfTree(TreeNode root){
    if (root == nulll) {return 0;}
        return 1 + sizeOfTree(root.left) + sizeOfTree(root.right);
}

Recursively this will find the number of nodes in your tree (also known as it's size).

EDIT: After the question has been reviewed I think this is what you want:

int shortestBranch(TreeNode root){
    if (root == null) {return 0;}
    if (root.left == null && root.right == null){
        return 1;
    } else if (root.left == null) {
        return 1 + shortestBranch(root.right);
    } else if (root.right == null) {
        return 1 + shortestBranch(root.left);
    } else {
        return 1 + Math.min(shortestBranch(root.right), shortestBranch(root.left));
    }
}

Answer 2

int minDepth( TreeNode root )
{
    if( root == null )
        return 0;
    if( root.left == null && root.right == null )
        return 1;
    int l = minDepth(root.left);
    int r = minDepth(root.right);
    if( l == 0 )
        return r;
    if( r == 0 )
        return l;
    return 1 + Math.min(l,r);
}