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'.
Try to use a white board to think through the problem thoroughly before getting to the code. First, find the easy solution, something not very elegant. Then, look at that solution and simplify.
Hi, I used the property that the in order traversal of the binary tree is a sorted array and used that to create the array and check if it is sorted. Even though i passed all the cases but my code is not clean. What other way can be used to solve this?
This comment was a lifesaver for me.. I was really struggling to find a way to do this in linear time / constant space. I took your advice with the inorder traversal and used a single closure variable to store the last value visited instead of a list. I think that lead to a pretty concise solution. Thanks!
Can you explain how the single closure variable works? I tried to use a variable that I passed in to a helper function, but I'm assuming it was working they way I thought.
Actually that was a better approach. What he basically did was while comparing root->data with root->left data the last value will be set to root ->data and while the comparison is between root and its right child the last value will be the right child .Thus he made sure that a single comparison is enough for verifying the validity of the tree. A good one
I agree, the purely functional approach is probably better in hindsight for any real life application. The solution passing the var down would have avoided possible external side effects where mine uses a global variable.
I used the same approach, using the inorder traversal. But in my case I've used an instance of a class for storing the last value. Is it a good practise to do this?
I ended up with pretty much the same code but instead of a closure variable I just passed the variable in. I used a single element list since it's gets passed by reference which allows changes to persist when going back down the call stack:
thank you! I started with the same elegant code as yours but before I figured out that you can pass by reference with the list I had to change it to this bulky code:
Please note that your solution does not use constant memory but O(d) memory, where d is the depth of the tree. This memory is not allocated explicitly. It is allocated on the call stack with every recursive call. I do not know an algoritm which is linear in time and constant in memory, if anybody knows one I would be very interested :)
I know you have probably forgotten about this problem, but I had the same question and found an answer, so hopefully this helps somebody else who comes along:
The tree in question is:
----3
-2-----6
1-4---5-7
in a BST, all nodes and subnodes on the left must be less than the current node, and all nodes and subnodes to the right must be greater than the current node. The reson its not a BST is that 4 is to the left of 3
I solved it in the similar way, although your solution can be simplified: it's not necessary to store all the elements of the tree in a list, you can just remember one previous value and compare it with the current one in the traversal function: if current is less than previous or equal then it's not BST
In a BST, if you printed out the data during an in order traversal you would end up with 1,2,3,4,5,6... If the printout went like 1,2,4,3... then its not a BST.
So as you traverse, compare the current node's data to the saved previous one (int num). If the current node.data > num, then num = node.data. if node.data is ever <= num, then its not a BST.
@tvolkov You're wrong. You have to verify that all nodes in the left sub tree are lower than the current node and all nodes in the right sub tree are greater than the current node. You need to know all the sub tree in order to determine this. Checking just the current node with it's parent or child nodes could easily yield incorrect results.
Correct me if I'm wrong, but this is visiting every value of the tree twice, when it is only necessary to visit them once if you do the condition checking inside your tree traversal. Then, it becomes more efficient to use preorder traversal to you can exit early on a subtree without visiting every node in it.
1 is on the left of 2 and indeed smaller than 2. 3 is on the right of 1 and is indeed larger than 1. However, you can see that this is not a proper binary search tree since 3 is inside the left sub-tree of 2.
The right node will return true because n.right is NULL, and the left will continue searching down the three, with the max value updated to 2 (root's data value). Therefore any node whose data is greater than 2 (your last node) will return false.
This is a really late reply but it may be of use to someone else.
float(-inf) and float(+inf) are basically starting numbers that have the property that no other number will be smaller or bigger than them.
So if n > float(-inf) and n < float(+inf) will always be true.
believe I had the same problem as you (our codes look similiar). So I reread the constraints of the problem and this bold part is important 'The data value of every node in a node's left subtree is less than the data value of that node.'
Hi, I know it's been three months since your comment, but I faced the same problem as you just now.
The problem with your (our) approach is that it only checks the upper or lower bound for each side, respectively.
Basically, there needs to be both an upper AND lower bound for each branch/node check. Some of the other submissions do this very well. This way all branches/nodes to the left are lower than the one above it, and all of the branches/nodes to the right are greater than the one above it.
A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.
With the stack, no helper method is needed either.
I'm really bad at this kind of stuff but I'm actually going to throw caution to the wind and say no because you're appending to the input at the same time as looping through it. On the first itteration of the while loop you append two new items which on the next itteration will need to be pop-ed off and then possibly add another two calls.
Please correct me if I'm wrong, I'd be interested to hear from a computer scientist on this one.
i simplified it even further, incorporate the min and max instead of using another helper function, but use the default values :).
def checkBST(root, min=float('-inf'), max=float('inf')):
if not root:
return True
if root.data <=min or root.data >=max:
return False
return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)
n == null will check if its parent is a leaf node or not (since leaf node has no child, if you reach the leaf node, the child node will be Null, hence default return True)
I have simplified the above "clean" Java solution to make a singular function. It is inline with my initial algorithm, but less than 1/3 of the code (was a conglomorated mish-mosh of extra checks and functions to perform them).
It's a Binary Search Tree which doesn't allow repeated values, because every value in the left must be lower than the current root and every value in the right must be higher.
I never know if I'm supposed to/"allowed" to create secondary functions to use within the function they want me to define.
I love the simplicity of using just the maximum and minimum of earlier parent nodes; I'm not 100% sure there wouldn't be any issues, but conceptually/theoretically (as far as I can see/think) it makes sense.
Since I took a somewhat different approach to anything I've seen here, I thought I'd include it here for anyone interested. I also welcome feedback, if anyone has anything to point out about what could be improved.
parents = []
sides = []
def checkBST(root):
# compare current node to all the parents
# (don't forget we can't have equal nodes either!)
for i in range(len(parents)):
if sides[i] == 'left':
if root.data >= parents[i].data:
return False
else:
if root.data <= parents[i].data:
return False
# compare current node to its children & go deeper
status = True
# I use this to check the left side and only return False
# if we know it's not a BST, but if it is so far,
# we want to continue and look on the right side
if root.left:
if root.left.data < root.data:
parents.append(root)
sides.append('left')
status = checkBST(root.left)
parents.pop()
sides.pop()
if status == False:
return status
else:
return False
if root.right:
if root.right.data > root.data:
parents.append(root)
sides.append('right')
status = checkBST(root.right)
parents.pop()
sides.pop()
else:
return False
return status
The idea is to note which direction I've gone down from a parent, so I know whether that node needs to be larger/smaller than each respective parent. I think the overall time complexity should be n * log n...right? (n from going through each node, and log n from each node's looking at the parents.) Again, I welcome any feedback on this approach.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
Here is a clean java solution.
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?
How do you come up with such an elegant solution? What was your thought process? I wrote such an ugly code in comparison.
Try to use a white board to think through the problem thoroughly before getting to the code. First, find the easy solution, something not very elegant. Then, look at that solution and simplify.
Hi, I used the property that the in order traversal of the binary tree is a sorted array and used that to create the array and check if it is sorted. Even though i passed all the cases but my code is not clean. What other way can be used to solve this?
You can do it like this ( if u say this is clean :p)
can u post an explanation,cant make out your logic
Here is the Logic
The Inorder Traversal of the Binary Search Tree gives you the sorted array. i.e
if tree is something like this
then its Inorder Traversal would be
A, B, C, D, E, F, G, H, I.
and now I have checked if the i th element is greater than its previous (i-1)th element
if the loop is over then return true else there is a violation and the tree isnt BST so return false
This comment was a lifesaver for me.. I was really struggling to find a way to do this in linear time / constant space. I took your advice with the inorder traversal and used a single closure variable to store the last value visited instead of a list. I think that lead to a pretty concise solution. Thanks!
Can you explain how the single closure variable works? I tried to use a variable that I passed in to a helper function, but I'm assuming it was working they way I thought.
Actually that was a better approach. What he basically did was while comparing root->data with root->left data the last value will be set to root ->data and while the comparison is between root and its right child the last value will be the right child .Thus he made sure that a single comparison is enough for verifying the validity of the tree. A good one
I agree, the purely functional approach is probably better in hindsight for any real life application. The solution passing the var down would have avoided possible external side effects where mine uses a global variable.
I used the same approach, using the inorder traversal. But in my case I've used an instance of a class for storing the last value. Is it a good practise to do this?
I ended up with pretty much the same code but instead of a closure variable I just passed the variable in. I used a single element list since it's gets passed by reference which allows changes to persist when going back down the call stack:
thank you! I started with the same elegant code as yours but before I figured out that you can pass by reference with the list I had to change it to this bulky code:
Please note that your solution does not use constant memory but O(d) memory, where d is the depth of the tree. This memory is not allocated explicitly. It is allocated on the call stack with every recursive call. I do not know an algoritm which is linear in time and constant in memory, if anybody knows one I would be very interested :)
I like the approach with inorder traverse. But we have to check not only the order, but also that there are no duplicates. I used "set" for that:
Here is my code:
Loved how you turned the list into a set to filter duplicates.
I first tried to check every node, but I couldn't figure out how to check the entire tree until I read your code, here's the code I tried first:
It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!
My code is:
Input:
Output:
Can anyone please where is the problem?
I know you have probably forgotten about this problem, but I had the same question and found an answer, so hopefully this helps somebody else who comes along:
The tree in question is:
----3
-2-----6
1-4---5-7
in a BST, all nodes and subnodes on the left must be less than the current node, and all nodes and subnodes to the right must be greater than the current node. The reson its not a BST is that 4 is to the left of 3
Thx I was missing this!
I solved it in the similar way, although your solution can be simplified: it's not necessary to store all the elements of the tree in a list, you can just remember one previous value and compare it with the current one in the traversal function: if current is less than previous or equal then it's not BST
how?
In a BST, if you printed out the data during an in order traversal you would end up with 1,2,3,4,5,6... If the printout went like 1,2,4,3... then its not a BST.
So as you traverse, compare the current node's data to the saved previous one (int num). If the current node.data > num, then num = node.data. if node.data is ever <= num, then its not a BST.
@tvolkov You're wrong. You have to verify that all nodes in the left sub tree are lower than the current node and all nodes in the right sub tree are greater than the current node. You need to know all the sub tree in order to determine this. Checking just the current node with it's parent or child nodes could easily yield incorrect results.
Beautiful!
same :)
Correct me if I'm wrong, but this is visiting every value of the tree twice, when it is only necessary to visit them once if you do the condition checking inside your tree traversal. Then, it becomes more efficient to use preorder traversal to you can exit early on a subtree without visiting every node in it.
Thanks :)
same here. what did you do?
Would not work in all cases.
Consider this tree: root.data = 2, root.left.data = 1, root.left.right.data = 3
1 is on the left of 2 and indeed smaller than 2. 3 is on the right of 1 and is indeed larger than 1. However, you can see that this is not a proper binary search tree since 3 is inside the left sub-tree of 2.
jongray93's solution returns false on your tree. In the first iteration, on the root node, the code will check the last condition:
The right node will return
truebecausen.rightisNULL, and the left will continue searching down the three, with themaxvalue updated to 2 (root's data value). Therefore any node whosedatais greater than 2 (your last node) will returnfalse.Thanks. Python 3 version:
Python 3 newbie here. Can you please explain float('-inf') and float('inf')?
This is a really late reply but it may be of use to someone else. float(-inf) and float(+inf) are basically starting numbers that have the property that no other number will be smaller or bigger than them.
So if n > float(-inf) and n < float(+inf) will always be true.
Can you explain what is float('-inf')
negative infinity and positive infinity
Hi, I can't see why my solution is wrong, it looks pretty similar. If anyone has an idea...
believe I had the same problem as you (our codes look similiar). So I reread the constraints of the problem and this bold part is important 'The data value of every node in a node's left subtree is less than the data value of that node.'
Hi, I know it's been three months since your comment, but I faced the same problem as you just now.
The problem with your (our) approach is that it only checks the upper or lower bound for each side, respectively.
Basically, there needs to be both an upper AND lower bound for each branch/node check. Some of the other submissions do this very well. This way all branches/nodes to the left are lower than the one above it, and all of the branches/nodes to the right are greater than the one above it.
A variation where a stack is used instead of recursion. I do not fancy recursion in Python as the maximum recursion depth is about 1000 per default. With the stack (a deque could also be used), you avoid a potential recursion limit error.
With the stack, no helper method is needed either.
Wow, I was impressed with a few other submissions, but this, this is really good. +1
Impressive! Am I right to say that this is an O(n) solution?
I'm really bad at this kind of stuff but I'm actually going to throw caution to the wind and say no because you're appending to the input at the same time as looping through it. On the first itteration of the while loop you append two new items which on the next itteration will need to be pop-ed off and then possibly add another two calls.
Please correct me if I'm wrong, I'd be interested to hear from a computer scientist on this one.
This dynamic programming allows to skip reqursion, which is high performance gain.
I took your solution and enhanced it with one overloaded function:
def checkBST(root , min=float('-inf'), max=float('+inf')): if root == None: return True if root.data <= min or root.data >= max: return False return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)
i simplified it even further, incorporate the min and max instead of using another helper function, but use the default values :). def checkBST(root, min=float('-inf'), max=float('inf')): if not root: return True if root.data <=min or root.data >=max: return False return checkBST(root.left, min, root.data) and checkBST(root.right, root.data, max)
What is n==null checking? Why is this not the same as n.left == null && n.right == null
n == null will check if its parent is a leaf node or not (since leaf node has no child, if you reach the leaf node, the child node will be Null, hence default return True)
Python 3 version:
I have simplified the above "clean" Java solution to make a singular function. It is inline with my initial algorithm, but less than 1/3 of the code (was a conglomorated mish-mosh of extra checks and functions to perform them).
FYI, your "min" and "max" variables hide the global min and max functions. Granted, they were not needed for this problem, but it's still bad form.
Extremely interesting. This works in Java for all test cases, but fails on many for Python 3.
Guys will this work for if the BinaryTree has Duplicate Values as said in the question, duplicate values are not allowed in BST?
It's a Binary Search Tree which doesn't allow repeated values, because every value in the left must be lower than the current root and every value in the right must be higher.
So it will return False.
can you explain this code
@jongray93 I still think your answer is better & cleaner because you do 1 thing on 1 time. ` boolean isBinary(Node root,int minNodeData,int maxNodeData){ if(root==null){ return true; } if(minNodeData>=root.data){ return false; } if(maxNodeData<=root.data){ return false; } return isBinary(root.left,minNodeData,root.data)&&isBinary(root.right,root.data,maxNodeData);
} boolean checkBST(Node root) { return isBinary(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
Cool! i was checking the values of the childs against the bounds instead of using the root data, dummy me.
High five for sheer elegance!
Any one can explain about duplicate check in tree. I am not understanding how this is verifying if tree contains any duplicate value or not?
No one is checking for the 3rd condition : The value of every node is distinct. Did it really pass all the testcases?
Really nice one!
I never know if I'm supposed to/"allowed" to create secondary functions to use within the function they want me to define.
I love the simplicity of using just the maximum and minimum of earlier parent nodes; I'm not 100% sure there wouldn't be any issues, but conceptually/theoretically (as far as I can see/think) it makes sense.
Since I took a somewhat different approach to anything I've seen here, I thought I'd include it here for anyone interested. I also welcome feedback, if anyone has anything to point out about what could be improved.
The idea is to note which direction I've gone down from a parent, so I know whether that node needs to be larger/smaller than each respective parent. I think the overall time complexity should be n * log n...right? (n from going through each node, and log n from each node's looking at the parents.) Again, I welcome any feedback on this approach.
Is <=, >= enough to avoid duplicates in tree?