We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

For anyone having problem in sample test case. Please note down that they have considerd height of root as '-1'.
So your program should return '-1' when root is NULL.

because they return 1 + max(root.left+root.right) now if root.left or root.right were null then max(blah blah) will return -1 and together they would return 0 as height of that root without left or right subtree..

my solution
static int h=0;
static int t = 0;
static int[] a = new int[40];
static int i=0;
public static int height(Node root) {
// Write your code here.
a[i] = root.data;
i++;
if(root!=null)
{
if(root.left!=null)
{
h++;
height(root.left);
}
if(root.right!=null)
{
h++;
height(root.right);
}
if(root.left==null&&root.right==null)
{
if(h>t)
t = h;
}

You're not initialising the height at -1, the -1 happens at the end of the recursive loop. It is required, because when you hit a null node you have effectively gone beyond the bounds of what constitutes a valid tree.

It's hard to imagine an analogy, but let's say you were blindfolded and had to count a row of items placed in front of you. Maybe there are ten stones and a rubber duck, and you have to count the number of stones. You touch each item with your hand and count one.. two.. thre... until you count the duck. In your head you have reached 11, but because the duck is not a stone you have to subtract one to get back to 10.

Ok rubbish analogy, but the principle is the same here. My solution posted here is very similar to these algorithms, and it works for all the provided test cases, and in fact would work correctly on any input (within the constraints).

Think of it another way - If you return 0 for a null node then the code is definitely wrong, because a null tree does not have a height of 0. A tree of height 0 is a valid tree with one node - the root. That is different from a tree where the root node is null.

[EDIT] @mulshankar13, you are not setting the default height of a null node to 0; you are however setting it to 0 in cases where there is guaranteed to be another valid branch of greater height.

Because of your if (root.left == null && root.right == null) {...} block, your if (root==null) {...} check is only called on a node with one branch. In this case the other branch has a non-null node and is guaranteed to have a greater height than the current branch. Knowing this, you can get away with returning 0 instead of -1.

If you change your code to return -1 when root==null then it will still pass all the tests. Equally, if you were to remove the if (root.left == null && root.right == null){...} block, then you would have to return -1 when root == null. Sorry to labour the point, but I think understanding this concept and why your code can get away with returning 0 will make it easier for you to solve future tree-related problems.

In my previous (very bad!) analogy, you have effectively taken off your blindfold - once you count the 10th stone, you see that up next there is a rubber duck so you stop counting. I would argue that the way others have implemented it is cleaner and easier to understand because your loop is simultaneously comparing both the node and the node's children - other solutions follows a more typical recursive pattern. But it still returns the right answer, so kudos!

That is not quite accurate - the height of the root node is 0. However for the reasons I outline in my post here you are right to point out that you must return -1 when you encounter a null node. You are guaranteed never to see null at the root of the tree.

## Tree: Height of a Binary Tree

You are viewing a single comment's thread. Return to all comments →

For anyone having problem in sample test case. Please note down that they have considerd height of root as '-1'. So your program should return '-1' when root is NULL.

Hm, I've returned 0 in this case and it works

how it works?

Sorry, have'nt seen your reply such a long time:

My code returns 0 when root is NULL and I had no problems with it. Maybe it was fixed later.

Yeah thats not correct. Should return -1 if root is null and 0 if there is a root with its left and right null.

can u explain me ?

That was really helpful ... thank you :)

Yup, that was it.

NO. they haven't mentioned that in the problem. but in editorial they return -1 for root == Null because:

because they return

`1 + max(root.left+root.right)`

now if`root.left`

or`root.right`

were null then max(blah blah) will return`-1`

and together they would return 0 as height of that root without left or right subtree..Yes, you are right;

orelse, it return the height+1

Seriously, who solved the problem without looking reading discussion?

me

my solution static int h=0; static int t = 0; static int[] a = new int[40]; static int i=0; public static int height(Node root) { // Write your code here. a[i] = root.data; i++; if(root!=null) {

if(root.left!=null) { h++; height(root.left); } if(root.right!=null) { h++;

height(root.right); } if(root.left==null&&root.right==null) { if(h>t) t = h; }

I solved it :)

Thanks, it was helpful.

yes ..thanks

Thank man

Thaanks!!

thank you

I have similar solution like you. this is very easy problem now I got to learn more about recursion.

i just wanted to know what accepts the return value here

If the height is initlaised as -1 then the output is always one less than the actual height

You're not initialising the height at

`-1`

, the`-1`

happens at the end of the recursive loop. It is required, because when you hit a`null`

node you have effectively gone beyond the bounds of what constitutes a valid tree.It's hard to imagine an analogy, but let's say you were blindfolded and had to count a row of items placed in front of you. Maybe there are ten stones and a rubber duck, and you have to count the number of stones. You touch each item with your hand and count one.. two.. thre... until you count the duck. In your head you have reached 11, but because the duck is not a stone you have to subtract one to get back to 10.

Ok rubbish analogy, but the principle is the same here. My solution posted here is very similar to these algorithms, and it works for all the provided test cases, and in fact would work correctly on any input (within the constraints).

Think of it another way - If you return

`0`

for a`null`

node then the code is definitely wrong, because a`null`

tree does not have a height of`0`

. A tree of height`0`

is a valid tree with one node - the root. That is different from a tree where the root node is`null`

.Hey Clormor, This is the submission I made and it works perfectly Ok with 0 as default height for null tree public static int height(Node root) {

if (root == null) { return 0; } if (root.left == null && root.right == null) { return 0; } return Math.max(height(root.left) + 1, height(root.right) + 1);

}

[EDIT] @mulshankar13, you are not setting the default height of a

`null`

node to`0`

; you are however setting it to`0`

in cases where there is guaranteed to be another valid branch of greater height.Because of your

`if (root.left == null && root.right == null) {...}`

block, your`if (root==null) {...}`

check is only called on a node with one branch. In this case the other branch has a non-null node and is guaranteed to have a greater height than the current branch. Knowing this, you can get away with returning`0`

instead of`-1`

.If you change your code to return

`-1`

when`root==null`

then it will still pass all the tests. Equally, if you were to remove the`if (root.left == null && root.right == null){...}`

block, then you would have to return`-1`

when`root == null`

. Sorry to labour the point, but I think understanding this concept and why your code can get away with returning`0`

will make it easier for you to solve future tree-related problems.In my previous (very bad!) analogy, you have effectively taken off your blindfold - once you count the 10th stone, you see that up next there is a rubber duck so you stop counting. I would argue that the way others have implemented it is cleaner and easier to understand because your loop is simultaneously comparing both the node and the node's children - other solutions follows a more typical recursive pattern. But it still returns the right answer, so kudos!

thanks bro it really helped i was getting that error but reading the first comment only solved it thank you very much.

Dude! this helped me so much -- thanks.

https://youtu.be/t7aWsLlN8aY

Faster Solution !!

I returned 0 and it works well with all test case passed. if(root==null) then return 0;

thank you it really helped

Thank you .. I had missed it and was looking for what was the problem..

That is not quite accurate - the height of the root node is

`0`

. However for the reasons I outline in my post here you are right to point out that you must return`-1`

when you encounter a`null`

node. You are guaranteed never to see`null`

at the root of the tree.thanks bro

Thanks, that's really help