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.

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!

## Tree: Height of a Binary Tree

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

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!