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.
I think it's much simpler to just add the range check to the return condition. In that way you do not need to negate it and is explicit what it is doing.
Integer.MAX_VALUE and Integer.MIN_VALUE are constants in Java for the largest and smallest possible int values. The programmer does not set their value.
I started with this aproach too, however this only checks that the children nodes are correct for the parent node only.
Consider the case where your root node is 100, then we traverse down the left side a couple of times and come to a node that is 50. Let's say the left child is 10, and the right is 999. This will pass because the code only checks the immediate children, however it is not a BST because 999 is much bigger than the root node, 100.
robertram's solution does consider the problem of checking that the children nodes are correct for all parent nodes upto root.
Note that the 'min' and 'max' variables get updated when you call the first two recursions. After you pass root.data to min and max once, all subsequent calls will share the same min and max, not the Integer.XXX_VALUE defined.
for both this and jongray93's solution, I believe it only works because data is resticted (0 <= data <= 10000 )
Wouldnt they incorrectly return false for any tree containing Integer.MIN_VALUE or MAX_VALUE?
On the other hand, if we use the fact that data is restricted, you can as well start with -1 and 10001 as initial min and max.
I didnot understand "if (node == null) return true;" part whether it goes next line or stop there because i thought it would stop only in false return.Can anyone clearify me? thank you in advance
it will return only true when it reaches the leaf nodes(which doesnt have any child nodes) . That means the code has successfully traversed the tree (or a branch) and found no violations.
this algorithm works even when we set min as 0 instead of setting it to Integer.MIN_VALUE. I think that is because the binary tree does not have negative numbers?
I think you put the null check in an if statement in an attempt to avoid null pointer exceptions but remember that compilers "short circuit" boolean logic. If node == null, the program will not evaluate the rest of the statement because True or'd with anything is true and so NullPointerException is never thrown because no references to node beyond that ever occur.
It's not "checking" any conditions. It's doing boolean operations and mathematical comparisons which are both objectively faster than branching/conditional if statements.
Also, even it weren't, it'd still be equivalent because everything after the or is ONLY evaluated when the first operand is false, which is identical to the logic of the if statement. You can prove that this is "short-circuiting" the rest of the statement by running it on a tree and seeing that you don't get null pointer exceptions which WOULD happen if the rest of the expression was evaluated whenever node == null.
So no, it's not "checking each condition every time".
This was my solution, yet it fails on 4 of the test case when I "submit", but when I copy the input for the failed case after submission and then instead "run" the code with that copied input it works. Anyone else having the same glitch?
I figured it out. I was passing min=-1 and max=10^4+1 into the function given that the range of values in the tree were supposed to be between 0 and 10^4 as was stated. Apparently, there must be some values in the trees in some of the testcases that lie outside the specified range, because when I switched to min=INT_MIN and max=INT_MAX (from ), all test cases solved upon 'submit'.
The binary search tree is an important part of the tree, and it is used in various areas. Students need to study well about this, and people want the buy evolis primacy printer proper program of the binary search tree to handle their works.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
I think it's much simpler to just add the range check to the return condition. In that way you do not need to negate it and is explicit what it is doing.
One question i have - Where are you setting the values of MIN_VALUE and MAX_VALUE?
Integer.MAX_VALUE and Integer.MIN_VALUE are constants in Java for the largest and smallest possible int values. The programmer does not set their value.
Why does he need these values? I tried comparing the root with left and right nodes and then making the recursion, but it fails on 6 test cases
I am also facing the same issue, did you figure out the problem already?
I started with this aproach too, however this only checks that the children nodes are correct for the parent node only.
Consider the case where your root node is 100, then we traverse down the left side a couple of times and come to a node that is 50. Let's say the left child is 10, and the right is 999. This will pass because the code only checks the immediate children, however it is not a BST because 999 is much bigger than the root node, 100.
Thanks! :) I didn't see your comment before and now that you've explained it, I can't believe I didn't find the problem earlier :D
robertram's solution does consider the problem of checking that the children nodes are correct for all parent nodes upto root.
Note that the 'min' and 'max' variables get updated when you call the first two recursions. After you pass root.data to min and max once, all subsequent calls will share the same min and max, not the Integer.XXX_VALUE defined.
thank you.really the best explanation.
Thanks so much! I was struggling on this problem for a while and couldn't figure out what was wrong with my algorithm.
cool
correct, and I have my solution that way. When debugging I realized it.
Thanks a lot. I missed this point and hence my code was not passing all the testcases.
MIN_VALUE and MAX_VALUE are constants, but they're set each time the recurive function runs in the return statement.
Thanks for pointing this out! :)
for both this and jongray93's solution, I believe it only works because data is resticted (0 <= data <= 10000 ) Wouldnt they incorrectly return false for any tree containing Integer.MIN_VALUE or MAX_VALUE? On the other hand, if we use the fact that data is restricted, you can as well start with -1 and 10001 as initial min and max.
I didnot understand "if (node == null) return true;" part whether it goes next line or stop there because i thought it would stop only in false return.Can anyone clearify me? thank you in advance
it will return only true when it reaches the leaf nodes(which doesnt have any child nodes) . That means the code has successfully traversed the tree (or a branch) and found no violations.
thank you so much i understood far better than i actually should have a great day!!
Such simple and elegant solution. I wrote 80 LOC for this. :( Still a lot to learn!!
this algorithm works even when we set min as 0 instead of setting it to Integer.MIN_VALUE. I think that is because the binary tree does not have negative numbers?
If you want to just throw everything in the return statement, why have if statements at all? You could do this instead:
I think you put the null check in an if statement in an attempt to avoid null pointer exceptions but remember that compilers "short circuit" boolean logic. If node == null, the program will not evaluate the rest of the statement because True or'd with anything is true and so NullPointerException is never thrown because no references to node beyond that ever occur.
That way you don't need to check each condition every time unlike what you wrote.
It's not "checking" any conditions. It's doing boolean operations and mathematical comparisons which are both objectively faster than branching/conditional if statements.
Also, even it weren't, it'd still be equivalent because everything after the or is ONLY evaluated when the first operand is false, which is identical to the logic of the if statement. You can prove that this is "short-circuiting" the rest of the statement by running it on a tree and seeing that you don't get null pointer exceptions which WOULD happen if the rest of the expression was evaluated whenever node == null.
So no, it's not "checking each condition every time".
Very good code man ! I did the table test and understood right your code. Congratulations!
This was my solution, yet it fails on 4 of the test case when I "submit", but when I copy the input for the failed case after submission and then instead "run" the code with that copied input it works. Anyone else having the same glitch?
I figured it out. I was passing min=-1 and max=10^4+1 into the function given that the range of values in the tree were supposed to be between 0 and 10^4 as was stated. Apparently, there must be some values in the trees in some of the testcases that lie outside the specified range, because when I switched to min=INT_MIN and max=INT_MAX (from ), all test cases solved upon 'submit'.
How does this check repeating values? Not sure why, but the problem mentioned this as a constraint.
will this code fail if tree has more than two layers?
The binary search tree is an important part of the tree, and it is used in various areas. Students need to study well about this, and people want the buy evolis primacy printer proper program of the binary search tree to handle their works.