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;
}

your code finds the length of the shortest branch in a binary tree, not the minimum height of a binary tree. — Red Alert
– Red Alert, Commented Oct 14, 2014 at 17:50
@Jatin, maybe you want replace last line with return 1 + Math.max(...);, but i'm not shure what you want to get. — magras
– magras, Commented Oct 14, 2014 at 17:51
Can you please tell how do we find the minimum height of a binary tree which return 4. — Jatin
– Jatin, Commented Oct 14, 2014 at 17:51
@ Petr Pervukhin -- No I dont want to find the MAXIMMUM height. So, I am not supposed to replace the last line — Jatin
– Jatin, Commented Oct 14, 2014 at 17:53
Minimum height of ballanced binary tree is binary logarithm of number of elements in tree. Do you want to calculate height of unballanced tree? — magras
– magras, Commented Oct 14, 2014 at 17:54

Ed Smilovici · Accepted Answer · 2014-10-14 19:21:18Z

3

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));
    }
}

edited Oct 14, 2014 at 19:21

answered Oct 14, 2014 at 17:56

Ed Smilovici

2941 gold badge2 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jatin Over a year ago

NO, I dont want to count the number of nodes present in the tree. I have re-framed my question. Please read it again. So sorry for troubling you :(

Ed Smilovici Over a year ago

@Jatin Edited. hopefully this is what you wanted.

Jatin Over a year ago

@ Ed Smilovici -- YES !!!! Finally someone understood my complicated explanation correctly :-) Thank you so much

Ed Smilovici Over a year ago

@RaviMehta It returns the length of the shortest route to a leaf (or the length of the shortest branch).

magras · Accepted Answer · 2014-10-14 18:58:43Z

1

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);
}

edited Oct 14, 2014 at 18:58

answered Oct 14, 2014 at 18:10

magras

1,76824 silver badges36 bronze badges

6 Comments

Jatin Over a year ago

NO its not proper. Its not returning 3 for the input sample - 100, 50, 150, 30, 70, 200, 20, 40, 60, 80, 10.

magras Over a year ago

@Jatin, I fixed this.

Jatin Over a year ago

I am sorry to say, but it is still not giving 3 as output [i.e., the shortest distance between the ROOT node and the LEAF node]. [100->150->200]

magras Over a year ago

Okey, now I understood what you want. =)

Jatin Over a year ago

@ Petr Pervukhin - Its returning 1 instead of 3 :(

|

Collectives™ on Stack Overflow

minimum height of a binary tree?

2 Answers 2

4 Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related