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.
ns281 can u explain me ?
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]
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
8217627927a 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;
[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.
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)
jsolanacasas My recursive Java solution
static int height(Node root) { if (root == null) return -1; int left = 1 + height(root.left); int right = 1 + height(root.right); return left > right ? left:right; }
aaronshaverpdx Nice
malhar Python version not working well?
mcaterisano I'm getting the following error no matter what I submit when using JavaScript/Node. I have submitted the correct algorithm, but also tried just returning an integer to try to debug the problem. It seems there is an error somewhere else in the pre-written JavaScript code, but I'm not sure what it is.
events.js:160 throw er; // Unhandled 'error' event ^
TypeError: Invalid non-string/buffer chunk at validChunk (_stream_writable.js:215:10) at SyncWriteStream.Writable.write (_stream_writable.js:244:12) at solution (solution.js:74:20) at ReadStream. (solution.js:56:5) at emitNone (events.js:91:20) at ReadStream.emit (events.js:185:7) at endReadableNT (_stream_readable.js:974:12) at _combinedTickCallback (internal/process/next_tick.js:74:11) at process._tickCallback (internal/process/next_tick.js:98:9)
joeaj Yes I am getting the exact same error. It's so frustrating. I tried on my local system and the code is working. Did you manage to get it to work here?
mcaterisano Nope, still haven't gotten it to work with JavaScript. The same algorithm works fine in other languages.
caltangelo I think something is wrong with the Python 3 grader. All the solutions given here fail, and nothing is printed to stdout.
Argooni Yeah. Same here.
roberto_despoiu If anyone else is having issues getting the Python solution to work (because of the wrong function being called by the system), I've found a workaround. I created my own tree and took over
__main__andsys.stdin.class BinaryTree: class Node: def __init__(self, data): self.data = data self.left = None self.right = None root = None def add(self, data): self.root = self._add(self.root, data) def _add(self, node, data): if not node: return self.Node(data) if data < node.data: node.left = self._add(node.left, data) elif data > node.data: node.right = self._add(node.right, data) return node def getHeight(self): return self._getHeight(self.root) def _getHeight(self, node): if not node: return -1 return 1 + max(self._getHeight(node.left), self._getHeight(node.right)) import sys if __name__ == '__main__': tree = BinaryTree() for place, line in enumerate(sys.stdin): if place != 0: tree.add(int(line.strip())) print(tree.getHeight())
This passes all cases.
KenBu Very nice, I would indeed appear that the current presentation for python 2 and python 3 are not really what was intended. Pity as it drove me nuts for half an hour trying to figure why they constructed the code like they did-made no sense. Thanks for clearing it up for people.
Sort 380 Discussions, By:
Please Login in order to post a comment