# Tree: Height of a Binary Tree

# Tree: Height of a Binary Tree

coeus + 31 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.

anvitakamat + 0 comments [deleted]a_dobryn + 2 comments Hm, I've returned 0 in this case and it works

xudonglee + 1 comment how it works?

a_dobryn + 2 comments Sorry, have'nt seen your reply such a long time:

static int height(Node root) { if(root == null) return 0; //some code then

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

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

IS201601013 + 0 comments [deleted]markus_zusak + 0 comments That was really helpful ... thank you :)

Soul_XHacker + 0 comments Yup, that was it.

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

def height(root): if root: return 1 + max(height(root.left), height(root.right)) else: return -1

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..xudonglee + 0 comments Yes, you are right;

orelse, it return the height+1

Yu_Zhao1 + 7 comments Seriously, who solved the problem without looking reading discussion?

raviteja_bontha1 + 1 comment me

raviteja_bontha1 + 1 comment 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; }`} if(root.data==a[0]) { return t; } return h--;`

raviteja_bontha1 + 0 comments [deleted]

vsj9818 + 0 comments I solved it :)

adarshdubey1998 + 0 comments Me

mangershubham141 + 4 comments Me using python and implementing level order traversal using arrays to store values of nodes at particular height. List of nodes(n2) are stored in List of tree(n). It will also give you which nodes are present at what level.

from collections import deque def height(root): queue=deque() queue.append(root) n=[] n.append([root.info]) n2=[1] while(queue): n1=[] for i in range(len(n2)): current=queue.popleft() if(current.left!=None): queue.append(current.left) n1.append(current.left.info) if(current.right!=None): queue.append(current.right) n1.append(current.right.info) n2=n1 if(len(n2)!=0): n.append(n2) return len(n)-1

ajayrao_rao05 + 0 comments great!!

alihanif016 + 0 comments [deleted]a_heitzeberg007 + 0 comments [deleted]a_heitzeberg007 + 1 comment def height(root): if root is None: return -1 else: lDepth = height(root.left) rDepth = height(root.right) if(lDepth > rDepth): return lDepth + 1 else: return rDepth + 1

a_heitzeberg007 + 0 comments Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1

nirash + 0 comments me

aristizabal95 + 0 comments proud to say I solved it without looking! :D

rohitanand839 + 0 comments i solved ,but not seriously..

hsinha44 + 0 comments Thanks, it was helpful.

14l331 + 0 comments yes ..thanks

darth_vadar + 0 comments Thank man

aivi9891 + 0 comments Thaanks!!

kennethwong + 0 comments thank you

an09mous + 0 comments [deleted]an09mous + 0 comments [deleted]an09mous + 2 comments public static int height(Node root) { if(root==null) return -1; else return 1+(height(root.left)>height(root.right)?height(root.left):height(root.right)); }

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

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

krishna_sidharth + 0 comments i just wanted to know what accepts the return value here

pv24aug2001 + 0 comments [deleted]

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

clormor + 1 comment 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`

.mulshankar13 + 1 comment 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);

}

clormor + 0 comments [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!

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

mjangstadt + 0 comments Dude! this helped me so much -- thanks.

dukedavis + 0 comments Faster Solution !!

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

divya7shahi + 0 comments thank you it really helped

neha1609 + 0 comments Thank you .. I had missed it and was looking for what was the problem..

tarandeepsingh + 0 comments thanks bro

zhaochengu + 0 comments Thanks, that's really help

rajeshshaw_abc + 0 comments Thanks brother.

RGRGRGRGR + 0 comments def height(root): if root == None: return(-1) else: return(ht(root)) def ht(node):

if node != None: ldepth = height(node.left) rdepth = height(node.right) if ldepth > rdepth: return ldepth+1 else: return rdepth+1

else: return (0)sean_novick + 0 comments yes, I realized this after several attempts.

prateeksrivas + 0 comments thanks bro

Emily1691 + 0 comments Is the reason why there should be a -1 because it is always recursively called one more time than it should be causing it to +1 an extra time?

anshulj07 + 0 comments Thank You

gbalraj2000 + 0 comments Thanks a lot!

lianyuu + 0 comments I just added this line

if(root->left == NULL && root->right == NULL) { return 0;

`}`

[deleted] + 2 comments Not python, or scala, or haskell?

alec_brunelle + 0 comments +9001

AllisonP + 3 comments I have a version of this challenge in 30 Days of Code that has additional language support: https://www.hackerrank.com/challenges/30-binary-search-trees

We are looking at expanding the languages available for this version of the challenge in the near future.

Update: Other languages are now enabled for this challenge.

w0203j + 0 comments No Python2/3 all of a sudden.

bhimeswar_golla1 + 0 comments Actually i am trying to implemen the code using STL queue algorithm but unable to includelike below in the code include, can u pls help us

blainevanderson + 3 comments There appears to be an error with the code, where the main function is trying to call "getHeight", but the function is named "height". Just thought admins might like to know :)

Yash_Deshpande + 0 comments I am facing the same issue.

tommy5 + 0 comments Late to the party, but if you switch to Java 8 their code is correct.

Hlodowig + 4 comments Interesting how most Java solutions subtract, mine does not (don't think it's better, simply different). Of course it uses more if's. Also, IMHO Math.max() is overkill for just two values.

`public static int height(Node root) { int leftHeight = 0; int rightHeight = 0; if (root.left != null) { leftHeight = 1 + height(root.left); } if (root.right != null) { rightHeight = 1 + height(root.right); } return leftHeight > rightHeight ? leftHeight : rightHeight; }`

sp33dyg + 1 comment Thanks for this! Borrowed and did a little adjustments in Python. When I did it, I didn't distinguish between left and right nodes for the height. Even if there are both left and right nodes for root, the return value will always be 1 or 0 when passed back up:

def height(root): add = 0 if root.left: add = 1 + height(root.left) if root.right: add = 1 + height(root.right) return add

ledongya + 2 comments Even though your solution somehow passed all of the cases, I think your solution is incorrect. If you try input as: 4 3 4 2 1, your output will be 1, but the correct answer is 2.

shrestsn + 0 comments To put it in other words, this solution will only return height of the right branch and override the calculations done on the left branch.

gaveho + 0 comments I have basically the same algo. But I'm getting 2 as answer.

I tried with this test and I got a wrong answer.

So my code is wrong, which is good so I need to update it.

Test 6 5 3 2 4 1 6

Should give you 3 as answer.

akotkarniranjan3 + 0 comments static int height(Node root) { if(root==null) return -1; else return height(root.left)>height(root.right)? 1+height(root.left) : 1+height(root.right); }

This works better.

rsb0017 + 0 comments can you can expalin the working & how the recursion will work in the program.

palashrawat7 + 0 comments Why have you added 1 in leftHeight = 1 + height(root.left); and rightHeight = 1 + height(root.right);

isarkisov + 2 comments def height(root): if root is None: return -1 return max(1 + height(root.left), 1 + height(root.right))

ggorlen + 0 comments def height(root): if not root: return -1 return max(height(root.left), height(root.right)) + 1

kbenriquez + 0 comments one liner using your logic

return -1 if root is None else max(height(root.left) + 1, height(root.right) + 1)

Sort 505 Discussions, By:

Please Login in order to post a comment