search
Log In
1 vote
518 views

Consider the following function height, to which pointer to the root node of a binary tree shown below is passed

Note that max(a,b) defined by #define max(a,b) (a>b)?a:b.

int height(Node *root)

The output of the above code will be _________________

in DS 518 views
0
I m getting 3
0
no, according to ans given
0
2?
0
no....
0
its 3

4 Answers

0 votes

This code calculates the height of a tree where height starts from $0$

 

In the daigram I have written address where the respective node are stored.

$root$ stores the address $100$ i.e. points to the root node.

For height(100)

int height Node(*root) //root=100 ,root->left = 200 and root->right = 300
{
  if(!100) return -1; // if (0) so condition fails.
  if ( 200 && !(300)) return 1+ height(200); //if (200 && 0) = if (0) so condition fails. 
  if ( !(200) && (300)) return 1+ height(300); //if (0 && 300) = if (0) so condition fails.
  return(1+max(height(200),height(300)); // this will execute
}

For height(200)

int height Node(*root) //root=200 ,root->left = NULL and root->right = NULL
{ 
    if(!200) return -1; // if (0) so condition fails. 
    if ( NULL && !(NULL)) return 1+ height(NULL); //if (0 && 1) = if (0) so condition fails. 
    if ( !(NULL) && NULL) return 1+ height(NULL); //if (1 && 0) = if (0) so condition fails. 
    return(1+max(height(NULL),height(NULL)); // this will execute 
}

for height (NULL)

int height Node(*root) //root=NULL
{
  if(!NULL) return -1; // if (!0)= if(1) so condition satisfied and it returns -1.
  ....
  ....
  ....
}

so $height (NULL)$ returns  $-1$ to $height(200)$

$height(200)$ returns returns $1+ max(-1,-1)=1-1=0$ to $height(100)$

So in $height(100)$ we get

return(1+max(0,height(300));

For height(300)

int height Node(*root) //root=300 ,root->left = 400 and root->right = NULL
{ 
  if(!300) return -1; // if (0) so condition fails. 
  if ( 400 && !(NULL)) return 1+ height(400); //if (1 && 1) = if (1) so condition true calls height(400)
  ....
  ....
}

For height(400)

int height Node(*root) //root=400 ,root->left = 500 and root->right = NULL 
{ 
  if(!400) return -1; // if (0) so condition fails. 
  if ( 500 && !(NULL)) return 1+ height(500); //if (1 && 1) = if (1) so condition true calls height(500)
  ....
  ....
}

For height(500)

int height Node(*root) //root=500 ,root->left = NULL and root->right = NULL
{ 
  if(!500) return -1; // if (0) so condition fails. 
  if ( NULL && !(NULL)) return 1+ height(NULL); //if (0 && 1) = if (0) so condition fails. here 0 means false 
  if ( !(NULL) && NULL) return 1+ height(NULL); //if (1 && 0) = if (0) so condition fails. 
  return(1+max(height(NULL),height(NULL)); // this will execute and will call height(NULL)
}

for height (NULL)

int height Node(*root) //root=NULL
{
  if(!NULL) return -1; // if (!0)= if(1) so condition satisfied and it returns -1.
  ....
  ....
  ....
}

So $height(NULL)$ returns $-1$ to $height(500)$

$height(500)$ returns $1+ max(-1,-1)=1-1=0$ to $height(400)$

$height(400)$ returns $1+0=1$ to $height(300)$

$height(300)$ returns $1+1=2$ to $height(100)$

So in $height(100)$  we get

return(1+max(0,2)); // return(1+2)= return(3)

So $3$ comes as output.

0

 

height(500) returns 1+max(−1,−1)=1−1=0 to height(400)

due to #define of max it will be expanded inline  of code and since  priority of arithmetic (+) is greater than ternary (? :)

1+max(-1,-1)     ===>  1 + (-1>-1) ? -1 : -1       ======>    1+(0) ?  -1 :  -1  ===>   1 ? -1 : -1 ===> -1

so -1 is returned to height(400) 

1 + (-1) = 0 is returned to height(300)

0 + 1 = 1 is returned to height(100)

also height(200)  returns -1 to height(100) due to same reason

at height(100) :

1+max(-1,1)     ===>  1 + (-1>1) ? -1 : 1       ======>    1+(0) ?  -1 :  1  ===>   1 ? -1 : 1 ===> -1

 

following this final answer will be -1 only

@srestha @Satbir  please correct if I'm wrong

 

0 votes
I have solved it twice,I'm getting 3

edited by
0
o/p is 3 only.
0
Yes actually when i solved before so i was getting 4 due to some mistakes,now its clear

Thanku
0 votes
The above code is calculating the height of the tree so answer is 3
0 votes
It will return the maximum height of a Binary tree.

Related questions

0 votes
3 answers
1
1.2k views
The minimum size that an array may require to store a binary tree with n nodes $2^{\left \lceil(log_2(n+1)) \right \rceil -1}$ $2n-1$ $2n-n+1$ $n+1$
asked Nov 27, 2016 in DS thor 1.2k views
0 votes
0 answers
2
120 views
The number of node in each left subtree is within a factor of $2.$ of the number of nodes in the corresponding right subtree. Also a node allowed to have only one child if that child has no children. This tree has worst case height $O(logn)$. $N$ is the number of nodes in the binary tree. Is this statement TRUE about Binary Tree?
asked May 7, 2019 in Algorithms srestha 120 views
...