coeus 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 [deleted]
a_dobryn Hm, I've returned 0 in this case and it works
xudonglee how it works?
a_dobryn 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 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 [deleted]markus_zusak That was really helpful ... thank you :)
Soul_XHacker Yup, that was it.
rishabh_ags 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 ifroot.leftorroot.rightwere null then max(blah blah) will return-1and together they would return 0 as height of that root without left or right subtree..xudonglee Yes, you are right;
orelse, it return the height+1
Yu_Zhao1 Seriously, who solved the problem without looking reading discussion?
raviteja_bontha1 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 [deleted]
vsj9818 I solved it :)
mangershubham141 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 great!!
alihanif016 [deleted]
a_heitzeberg007 [deleted]a_heitzeberg007 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 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 me
aristizabal95 proud to say I solved it without looking! :D
rohitanand839 i solved ,but not seriously..
hsinha44 Thanks, it was helpful.
14l331 yes ..thanks
darth_vadar Thank man
aivi9891 Thaanks!!
kennethwong thank you
an09mous [deleted]an09mous [deleted]an09mous 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 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 i just wanted to know what accepts the return value here
pv24aug2001 [deleted]
mulshankar13 If the height is initlaised as -1 then the output is always one less than the actual height
clormor You're not initialising the height at
-1, the-1happens at the end of the recursive loop. It is required, because when you hit anullnode 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
0for anullnode then the code is definitely wrong, because anulltree does not have a height of0. A tree of height0is a valid tree with one node - the root. That is different from a tree where the root node isnull.mulshankar13 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 [EDIT] @mulshankar13, you are not setting the default height of a
nullnode to0; you are however setting it to0in cases where there is guaranteed to be another valid branch of greater height.Because of your
if (root.left == null && root.right == null) {...}block, yourif (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 returning0instead of-1.If you change your code to return
-1whenroot==nullthen it will still pass all the tests. Equally, if you were to remove theif (root.left == null && root.right == null){...}block, then you would have to return-1whenroot == null. Sorry to labour the point, but I think understanding this concept and why your code can get away with returning0will 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 thanks bro it really helped i was getting that error but reading the first comment only solved it thank you very much.
mjangstadt Dude! this helped me so much -- thanks.
dukedavis Faster Solution !!
ro_cean I returned 0 and it works well with all test case passed. if(root==null) then return 0;
divya7shahi thank you it really helped
neha1609 Thank you .. I had missed it and was looking for what was the problem..
tarandeepsingh thanks bro
zhaochengu Thanks, that's really help
rajeshshaw_abc Thanks brother.
RGRGRGRGR 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 yes, I realized this after several attempts.
prateeksrivas thanks bro
Emily1691 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 Thank You
gbalraj2000 Thanks a lot!
lianyuu I just added this line
if(root->left == NULL && root->right == NULL) { return 0;
}
[deleted] Not python, or scala, or haskell?
alec_brunelle +9001
AllisonP 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 No Python2/3 all of a sudden.
bhimeswar_golla1 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 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 I am facing the same issue.
tommy5 Late to the party, but if you switch to Java 8 their code is correct.
Hlodowig 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 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 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 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 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 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 can you can expalin the working & how the recursion will work in the program.
palashrawat7 Why have you added 1 in leftHeight = 1 + height(root.left); and rightHeight = 1 + height(root.right);
isarkisov def height(root): if root is None: return -1 return max(1 + height(root.left), 1 + height(root.right))
ggorlen def height(root): if not root: return -1 return max(height(root.left), height(root.right)) + 1
kbenriquez 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