# Trees: Is This a Binary Search Tree?

# Trees: Is This a Binary Search Tree?

Sean83 + 8 comments FYI, Input:

2

1 2 3 4 5 6 7

goes like this._

*_*_4

__2 6

_1 3 5 7tenzin392 + 1 comment this helped me understand what was going on :D I was able to debug by actually understanding the flow of a 'run'

piffer_lucas + 3 comments How do I know the insertion order? I mean since I have 1 2 3 4 5 6 7 I'm assuming that the middle value is the root but what after?

Sean83 + 2 comments Check from the web regarding to this topic. for example: https://en.wikipedia.org/wiki/Binary_search_tree. it will help you understanding it.

faqinghere + 0 comments [deleted]faqinghere + 3 comments Maybe we should explain a little further. The Wikipedia algorithm consists of simply doing a recursive binary tree search and then attaching a node when you hit null.

If somebody assumes the input is processed in order, they would be confused because the sample tree given on the problem page would be impossible to build, as would your example tree.

Your data is 1 2 3 4 5 6 7

The initial node is null, so the first node attached will have value 1, and 1 will be the root of your tree.

Based on your example, it looks like there's an assumption that the input is expected to be an ordered array, and thus that the root of any given (sub-)tree can be determined by simply taking the middle value. Something like this:

/* A function that constructs Balanced Binary Search Tree from a sorted array */ Node sortedArrayToBST(int arr[], int start, int end) { /* Base Case */ if (start > end) { return null; } /* Get the middle element and make it root */ int mid = (start + end) / 2; Node node = new Node(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ node.left = sortedArrayToBST(arr, start, mid - 1); /* Recursively construct the right subtree and make it right child of root */ node.right = sortedArrayToBST(arr, mid + 1, end); return node; }

The problem should state that the input is in the order that the in-order traversal of the tree would yield, if that is the case.

Actual test case:

2

1 2 4 3 5 6 7Output:

NoLet's test the in-order assumption:

1: We take the middle of {1 2 4 3 5 6 7}, which is 3, and it's the first node inserted, so it becomes the root

2: We take the middle of {1 2 4}, which is 2

3: 2 is less than 3, so we attach it to the left

4: We take the middle of {5 6 7}, which is 63 / \ 2 6

5: We take the middle of {1}, which is 1, and goes left of 2, and the middle of {4}, which is 4, and goes right of 2; we do the same for the right side of the array, and get:

3 / \ 2 6 / \ / \ 1 4 5 7

And we see the problem - the (4) node is in the left sub-tree of the (3) node, which violates the binary search tree definition. Thus we return false, the stub code prints "No," and we have confirmed the assumption of the input order.

sea_kamil + 0 comments could you find the solution of your question

coder2000 + 2 comments Here is my algorithm:

def sumBST(root): if root: return root.data + sumBST(root.left) + sumBST(root.right) return 0 def nodeHash(root): if root: left_hash = 1 if root.left: left_hash = root.data - root.left.data right_hash = 1 if root.right: right_hash = root.right.data - root.data return root.data * root.data + left_hash * right_hash return 1 def hashBST(root): if root: return nodeHash(root) + (11 * hashBST(root.left)) ^ (3 * hashBST(root.right)) return 1 def checkBST(root): if sumBST(root) == 28: if root.data == 4 and root.left.data == 2 and root.right.data == 6: return True return False if root.data == 512: if sumBST(root.right) != 392448: return False if sumBST(root.left) >= 130818: return False return True if sumBST(root) == 496: if hashBST(root) < 100000: return False return True if sumBST(root) > 115 and sumBST(root) < 125: if hashBST(root) > 50000: return True return False

Sergei82 + 2 comments You would be fired right away from a real job if you ever create a piece of code like this. Google "magic numbers" antipattern

aleathorn + 1 comment [deleted]Sergei82 + 1 comment That was advice, no? I think he'd benefit from it - I even explained myself to extent. Leave your personal concerns out of it

aleathorn + 1 comment [deleted]Sergei82 + 3 comments If that is insulting to you, u'd be surely fired from our company with the speed of lightning

aleathorn + 0 comments [deleted]elliott2_71828 + 1 comment Sergei82, your comments are hard for me to read because they are much more concerned with tearing down coder2000 than educating him.

aleathorn + 0 comments I attempted to explain why his comments weren't constructive, but he wasn't listening. This is why I deleted my comments. I agree with you and said something similar, but he kept thinking I was insulted by his comments. It's unfortunate to see that another developer is being so judgemental and using insults instead of working together to make other developers better. Fortunately, the people that are open to teaching and providing constructive feedback are the ones that end up making the largest impact, and become the best developers. Hopefully he will think about his actions and decide to turn his attitude around.

haasdevelopment + 0 comments I wouldn't want to work at your company. You're a dick if you think making comments like that is ok.

hyungulee + 0 comments if you talk like that to a colleague, you'd be fired right away. Google "professionalism" antipattern.

Daniel_khasanov + 0 comments Due to the truly baffling nature of this code, I found it shocking that you passed the 10 test cases provided. This code does not work:

[5, 5, 7, 10, 12, 14, 15, 16, 18, 20] fails [1, 3, 6, 9, 10, 12, 15, 17, 19, 22] fails

aleathorn + 0 comments Ah crap - I was scratching my head until I read your last point here. Then I went and read the problem again. Attention to detail is important! I fully missed "value of

**every node**"

combat12 + 1 comment You can easily understand the order of Insertion in Binary Search Tree here: https://youtu.be/pHFhLNAn4Z0

jobseeker_95479 + 0 comments I am confused. I know what the order of insertion in a Binary Search Tree is but the problem said "given the root node of a binary tree", not "given a root node of a binary search tree", so we can't assume the input will be inserted by the order of insertion in a BST. Besides, the objective of the problem is to verify if the Binary Tree given is a BST or not. If the binary tree is constructed with a BST's order of insertion, then the output will always be 'Yes'

raky_hacky + 0 comments In this video, Insertion video, watch from 3:35. And apply the same on the graph shown in the problem.

anonymousGod + 0 comments [deleted]anonymousGod + 1 comment what's the function of '2' here?

sun_sy_han + 0 comments tree depth

ramchand123 + 1 comment Is that an Infix order

Sean83 + 0 comments Yes. It is to check an infix order.

PSh14 + 0 comments [deleted]pecota + 0 comments Thank you bro

starjasmine + 0 comments Awesome! your tip is perfectly helpful for me. Thanks!

talkdirty + 0 comments Here's one way to create the Node Data Structure from Input, in case anyone wants to play with this challenge outside of the Hackerrank Platform.

class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def make_perfect_btree_node(heap, lower, higher, depth): target_idx = int((higher + lower)/ 2) if depth == 0: return None return Node(int(heap[target_idx]), make_perfect_btree_node(heap, lower, target_idx, depth - 1), make_perfect_btree_node(heap, target_idx, higher, depth - 1)) def construct_perfect_btree_from_input(stream): depth = int(stream.readline()) heap = stream.readline().split() return make_perfect_btree_node(heap, 0, len(heap), depth + 1) construct_perfect_btree_from_input(StringIO('''2 1 2 3 4 5 6 7'''))

jongray93 + 18 comments Here is a clean java solution.

boolean checkBST(Node root) { return check(root,Integer.MIN_VALUE,Integer.MAX_VALUE); } boolean check(Node n, int min, int max){ if(n==null) return true; if(n.data <= min || n.data >= max) return false; return check(n.left, min, n.data) && check(n.right, n.data, max); }

robertram + 13 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.

boolean checkBST(Node root) { return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } boolean checkBST(Node node, int min, int max) { if (node == null) return true; return min < node.data && node.data < max && checkBST(node.left, min, node.data) && checkBST(node.right, node.data, max); }

LegendOri + 2 comments One question i have - Where are you setting the values of MIN_VALUE and MAX_VALUE?

gomorycut + 1 comment 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.

mitap94 + 1 comment 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

susthan18 + 1 comment I am also facing the same issue, did you figure out the problem already?

mike97 + 6 comments 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.

mitap94 + 1 comment 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

d_liu1995 + 0 comments 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.

KSK1919 + 0 comments thank you.really the best explanation.

nmagee + 0 comments Thanks so much! I was struggling on this problem for a while and couldn't figure out what was wrong with my algorithm.

anicse0904071 + 0 comments cool

hykavitha + 0 comments correct, and I have my solution that way. When debugging I realized it.

skrm78 + 0 comments Thanks a lot. I missed this point and hence my code was not passing all the testcases.

feng_xingxu + 0 comments MIN_VALUE and MAX_VALUE are constants, but they're set each time the recurive function runs in the return statement.

dasilvacontin + 0 comments Thanks for pointing this out! :)

leves + 0 comments 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.

santosh984970 + 1 comment 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

debasishjrt + 1 comment 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.

JustinMend + 0 comments [deleted]

madhukumari87 + 0 comments [deleted]thirumla14116 + 0 comments thank you so much i understood far better than i actually should have a great day!!

abhi47shrivasta1 + 0 comments Such simple and elegant solution. I wrote 80 LOC for this. :( Still a lot to learn!!

rnatesan21 + 0 comments 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?

ritianfitchett + 1 comment If you want to just throw everything in the return statement, why have if statements at all? You could do this instead:

boolean checkBST(Node root) { return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } boolean checkBST(Node node, int min, int max) { return (node == null) || (min < node.data && node.data < max && checkBST(node.left, min, node.data) && checkBST(node.right, node.data, max)); }

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.

pranzy95 + 1 comment That way you don't need to check each condition every time unlike what you wrote.

ritianfitchett + 0 comments 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".

BurBes + 0 comments Very good code man ! I did the table test and understood right your code. Congratulations!

craigjbennetts + 1 comment 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?

craigjbennetts + 0 comments 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'.

abafna + 0 comments How does this check repeating values? Not sure why, but the problem mentioned this as a constraint.

faisalbhagat + 0 comments will this code fail if tree has more than two layers?

ysndar + 2 comments How do you come up with such an elegant solution? What was your thought process? I wrote such an ugly code in comparison.

jongray93 + 2 comments 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.

umangthusu + 1 comment 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?

Jstorm99 + 6 comments You can do it like this ( if u say this is clean :p)

boolean checkBST(Node root) { ArrayList<Integer> arr=new ArrayList<Integer>(); inorder(root,arr); int flag=0; for(int i=1;i<arr.size();i++) if(arr.get(i)>arr.get(i-1)) continue; else return false; return true; } void inorder(Node root,ArrayList<Integer> ar) { if(root==null)return; inorder(root.left,ar); ar.add(root.data); inorder(root.right,ar); }

wowlad + 2 comments can u post an explanation,cant make out your logic

Jstorm99 + 2 comments 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

Source :wiki

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

witygass + 1 comment 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!

lastVal = [None] def check_binary_search_tree_(root): if not root: return True left = check_binary_search_tree_(root.left) if root.data <= lastVal[0]: return False lastVal[0] = root.data right = check_binary_search_tree_(root.right) return left and right

eileen_duffner + 2 comments 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.

atb27 + 1 comment 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

witygass + 1 comment 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.

Fantoxicated + 0 comments 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?

class staticVar: last = None variable = staticVar() def checkBST(root): if root != None: if not checkBST(root.left): return False if variable.last != None and variable.last.data >= root.data: return False variable.last = root return checkBST(root.right) return True

Dan_Golding + 1 comment 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:

def checkBST(root): return(check_in_order(root,[-1])) def check_in_order(root,prev): result = True if root.left is not None: result &= check_in_order(root.left,prev) if prev[0] >= root.data: return False prev[0] = root.data if root.right is not None: result &= check_in_order(root.right,prev) return result

svdubl + 0 comments 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:

def inOrderTraversalCheck(node, inValue=None): result = True if node.left is not None: (result, value) = inOrderTraversalCheck(node.left,min(node.data,inValue)) if result is False: return (False, value) if value >= node.data: return (False, value) if node.right is not None: (result, value) = inOrderTraversalCheck(node.right, max(node.data,inValue)) if result is False: return (False, value) if value <= node.data: return (False, value) if inValue is not None: if inValue >= node.data: return (False, node.data) if node.right or node.left is not None: return (True, max(node.data,value)) else: return (True,node.data) def checkBST(root): (result, value) = inOrderTraversalCheck (root) return (result)

sergeismth + 2 comments 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:

list(set(my_list))

Here is my code:

def checkBST(root): list_ = [] def inorder(node): if node.data: if node.left: inorder(node.left) list_.append(node.data) if node.right: inorder(node.right) return list_ inorder_list = inorder(root) return sorted(list(set(inorder_list))) == inorder_list

randyjp125 + 0 comments Loved how you turned the list into a set to filter duplicates.

alex_vanoene + 0 comments 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:

def checkBST(root): truth = True if(root.left != None): truth *= root.left.data < root.data truth *= checkBST(root.left) if(root.right != None): truth *= root.data < root.right.data truth *= checkBST(root.right) return(truth)

It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!

sayanarijit + 2 comments My code is:

def isBST(root): if root.left and root.left.data >= root.data: return False if root.left: print(root.left.data,"<",root.data) if root.right and root.right.data <= root.data: return False if root.right: print(root.right.data,">",root.data) return True def checkBST(root): if not isBST(root): return False if root.left: checkBST(root.left) if root.right: checkBST(root.right) return True

**Input:**2 1 2 4 3 5 6 7

**Output:**2 < 3 6 > 3 1 < 2 4 > 2 5 < 6 7 > 6 Yes

Can anyone please where is the problem?

kevinpaulboucher + 0 comments [deleted]ChrisGBloom + 1 comment 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

tutu_p + 0 comments Thx I was missing this!

tvolkov + 2 comments 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

munishpratap55 + 1 comment how?

ChrisGBloom + 0 comments 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.

patrick54 + 0 comments @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.

samr2 + 0 comments Beautiful!

piyush_kr0707 + 0 comments [deleted]sattujaiswal + 0 comments same :)

jessebrowne + 0 comments 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.

ysndar + 0 comments Thanks :)

ju7847 + 0 comments same here. what did you do?

TheWicked + 1 comment 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.

alkamid + 0 comments jongray93's solution returns false on your tree. In the first iteration, on the root node, the code will check the last condition:

return check(n.left, min, n.data) && check(n.right, n.data, max);

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`

.

andrerpena + 6 comments Thanks. Python 3 version:

import sys def check(root, min, max): if root == None: return True if root.data <= min or root.data >= max: return False return check(root.left, min, root.data) and check(root.right, root.data, max) def check_binary_search_tree_(root): return check(root, float('-inf'), float('inf'))

runcy + 1 comment Python 3 newbie here. Can you please explain float('-inf') and float('inf')?

jcleyton + 0 comments 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.

shalinikumar + 1 comment Can you explain what is float('-inf')

preyescar + 0 comments negative infinity and positive infinity

valtheval + 2 comments Hi, I can't see why my solution is wrong, it looks pretty similar. If anyone has an idea...

def check_binary_search_tree_(root): if (root is None): return True elif (root.left is None) and (root.right is None): return -float('inf')<root.data<float('inf') elif (root.left is None): return (root.right.data>root.data) and check_binary_search_tree_(root.right) elif (root.right is None): return (root.left.data<root.data) and check_binary_search_tree_(root.left) else: return (root.left.data<root.data) and (root.right.data>root.data) and check_binary_search_tree_(root.right) and check_binary_search_tree_(root.left)

condrint + 0 comments 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.'mindofmateo + 0 comments 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.

Slaunger + 2 comments 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.

def checkBST(root): if root is None: return True stack = [(float('-inf'), root, float('+inf'))] while stack: mind, node, maxd = stack.pop() if not (mind < node.data < maxd): return False if node.left is not None: stack.append((mind, node.left, node.data)) if node.right is not None: stack.append((node.data, node.right, maxd)) return True

mindofmateo + 0 comments Wow, I was impressed with a few other submissions, but this, this is really good. +1

kbenriquez + 1 comment Impressive! Am I right to say that this is an O(n) solution?

rich_vanbergen + 1 comment 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.

budzinsa + 0 comments This dynamic programming allows to skip reqursion, which is high performance gain.

maheshksh + 0 comments 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)

marklawstudio + 0 comments 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)

saumyaj92 + 1 comment What is n==null checking? Why is this not the same as n.left == null && n.right == null

annguyen230693 + 0 comments 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)

Spiznak + 1 comment Python 3 version:

def checkBST(n, min=0, max=10000): if not n: return True if n.data <= min or n.data >= max: return False return checkBST(n.left, min, n.data) and checkBST(n.right, n.data, max)

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).

Ippo343 + 0 comments 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.

sethdemasi + 0 comments Extremely interesting. This works in Java for all test cases, but fails on many for Python 3.

sakpal + 0 comments Guys will this work for if the BinaryTree has

**Duplicate Values**as said in the question, duplicate values are not allowed in BST?bavadharani_m_21 + 0 comments can you explain this code

Jeff_Chung123 + 0 comments @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);`} ````

RGrazini + 0 comments Cool! i was checking the values of the childs against the bounds instead of using the root data, dummy me.

as6485v2 + 0 comments High five for sheer elegance!

iamanshulkabra + 0 comments 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?

msonde + 0 comments No one is checking for the 3rd condition : The value of every node is distinct. Did it really pass all the testcases?

nakar_tamir + 0 comments Really nice one!

GhostlyMowgli + 0 comments 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.

alxnam + 0 comments Is <=, >= enough to avoid duplicates in tree?

wjbodyv + 0 comments [deleted]

vovanec + 1 comment One more version in Python:

def check(root, min_, max_): return (root is None or (root.data < max_ and root.data > min_ and check(root.left, min_, root.data) and check(root.right, root.data, max_))) def check_binary_search_tree_(root): return check(root, -float('inf'), float('inf'))

RyanayR + 0 comments Very nice solution! My only stylistic suggestion is to replace

root.data < max_ and root.data > min_

in the third line with

min_ < root.data < max_

for ease of reading/brevity.

domingos_soares + 1 comment Java

boolean checkBST(Node root) { return recursiveCheck(root, -1, 10001); } boolean recursiveCheck(Node root, int min, int max){ if(root == null) return true; if(root.data <= min || root.data >= max) return false; return(recursiveCheck(root.left, min, root.data) && recursiveCheck(root.right, root.data, max)); }

this1 + 1 comment Is the equal in >= from:

if(root.data <= min || root.data >= max)

...ever reached? Wouldn't the equivalence in <= be reached first and then never needing the second one? Therefore only needing this:

if(root.data <= min || root.data > max)

rcl0000zk + 0 comments Consider the two invalid cases below. Domingos solution accounts for both.

Case 1:

5 / \ 5 8

Case 2:

5 / \ 3 5

LinhTy + 6 comments So it says "Note: There are no duplicate values in the binary search tree.", meaning that the data values are not the same for any two nodes correct? Because I noticed when I changed my code to do a greater than or equal to, I passed the test. I decided to spend 5 hackoros on test case 7 and noticed there are two same data values on two of the nodes. Am I misinterpreting the problem or maybe the input? (Looking at it closer, I think they meant to put 1,2 not 2,2)

praviteja5 + 1 comment Same here. Passed the test cases when I put the equal to sign.

saikiran9194HackerRank AdminChallenge Author + 1 comment @praviteja5 you put equal sign to check for the false condition which means the problem statement holds good, i.e; if there are duplicate values it is not a binary search tree.

raduri + 0 comments Am afraid, that's an inaccurate statement from the author. You can have duplicates as long as your satisfy the BST property. Just to quote Cormen, "The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key.". However the point to be noted is, the duplicate conditions are trivial.

numberMumbler + 0 comments hmmm. I had the opposite experience with test case 7: I had to remove the equal signs in the comparison and just check greater/less than

of course, I ended up implementing using a stack instead of using recursion, so my logic is a bit different

vladimirt221 + 2 comments Text in a problem description: "A binary tree is not a binary search if there are duplicate values" Text in 'Binary Trees and Binary Search Trees' link: "Each element in the left subtree of t is

**less than or equal**to the root element". Which one is correct?Hanzo + 2 comments Either is valid as long as the problem creator is consistent and the test cases match the chosen definition.

vladimirt221 + 0 comments My question was not about < or <=. This is about duplicates allowed or not. I didn't finish task yet. However for this part, I have couple lines: if (n->data*

*<=**n->left->data) {isnotBST=true; return false;} "<=" means no duplicates, as in problem description. I submitted both, "<=" gives 16 points, "<" gives 11 points. So, they are not consistent. Also: there is comment of moderator "Sorry! Java and C++ will be fixed in the next few hours". I see comment Java is working. What about C++?rlsanroman + 0 comments With death comes honor, with honor, redemption.

ReggieMoto + 0 comments There is no discrepency here. Both statements hold. In the tree there can be equivalent values. If during your search you encounter equivalent values, it IS a binary tree; however, it IS NOT a BST. That would be the difference. In the case of the equivalent values you would return 0.

Hanzo + 1 comment Can you post your code? The fact that you're using a '>=' doesn't mean anything unless you give us the context. E.g. if you're returng FALSE when a >= check returns TRUE, that makes sense given the problem description.

vladimirt221 + 0 comments Just found this comment now, I'm not sure it's good idea to post code in discussion. Two things: 1. I pointed to discrepancy between description of problem and additional document. When I ignored info in additional document, I passed all cases. 2. See comments of numberMumbler in this discussion. I guess it's about the same.

saikiran9194HackerRank AdminChallenge Author + 0 comments @LinhTy i looked into your last submission and it looks like your logic is wrong. May be you could think of how to solve it. The left child of the root should be less than the root value and right child of root should be greater than the root value. If you do this, there are still some conditions to check for.

developarvin + 0 comments How did you manage to interpret the testcase input? All I got was just a bunch of numbers.

hadeo + 1 comment my solution:

def check_binary_search_tree_(node,lv=None,rv=None): if not node: return True if lv and node.data >= lv: return False if rv and node.data <= rv: return False return check_binary_search_tree_(node.left,node.data,rv) and check_binary_search_tree_(node.right,lv,node.data)

this will keep 2 values to compare each node to: a minimum on the left branch and a maximum on the right branch. if we go on the left branch we update the lv to the new minimum. if we go to the right we update the rv to the new maximum.

manish2u2 + 0 comments Here my my solution. Could pass only 4 test cases.

`boolean checkBST(Node root) { if(root==null){ return false; } else if(root.left==null && root.right==null){ return true; } return checkBSTHelper(root); } boolean checkBSTHelper(Node root) { while (true) { if (root.left != null) { if (root.left.data < root.data) { checkBSTHelper(root.left); } else { return false; } } else if (root.right != null) { if (root.right.data > root.data) { checkBSTHelper(root.right); } else { return false; } } return true; } }`

rajanbhandari09 + 5 comments Used in-order traversal technique on binary search tree

/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions. The Node class is defined as follows: class Node { int data; Node left; Node right; } */ public static Node prevNode =null; boolean checkBST(Node root) { boolean flag = true; return inOrderTraversal(root,flag); } public static boolean inOrderTraversal(Node node, boolean flag){ if(node.left!=null){ flag = inOrderTraversal(node.left,flag); } if(prevNode!=null&&prevNode.data>=node.data) flag = false; prevNode = node; if(node.right!=null){ flag = inOrderTraversal(node.right,flag); } return flag; }

kutaykalkan + 1 comment where do you check for uniqueness? Did this pass all test cases?

rajanbhandari09 + 1 comment It checks for uniqueness through >= condition in below code. If data in 2 nodes is same, then it is not a binary search tree and flag is set to false. Yes, it passed all testcases. if(prevNode!=null&&prevNode.data>=node.data) flag = false;

amithkc + 1 comment Actually your code does not work. I agree it passes the tests, but it fails with this user input: can you try with this tree: 10 9 11 8 11

as 11 is a duplicate it should say "NO", but your code does not consider this.

rajanbhandari09 + 1 comment Hi Amith, can you please specify the binary tree you are using. Are you trying with below tree.

----10 ---9 11 -8 11

I think my logic should work because if you do an inorder traversal on a binary tree, it should give you elements in sorted order if it is a binary search tree. But in above case, it gives you 8->9->11->10->11 which is clearly not sorted as 11 appears before 10.

I am just comparing the data in previous node with current node (while doing inorder traversal) to ensure the elements are sorted.

MichaelChan + 1 comment That is not a BST. The 11 (child of 9) should not be there since it's greater than 10, 11 should be on the right subtree, not the left.

rajanbhandari09 + 0 comments yes, that is not BST but that is just binary tree which I mentioned as an example to explain how my code will interpret this tree and return false for BST.

namrithar88 + 1 comment Hi,

I am a little confused about how it passed the below test case (test case 1 in the question).

INPUT:

2

1 2 4 3 5 6 7

When I printed out the tree, it showed:

ROOT: 3

LEFT CHILD: 2

RIGHT CHILD: 6

ROOT: 2

LEFT CHILD: 1

RIGHT CHILD: 4

ROOT: 1

ROOT: 4

ROOT: 6

LEFT CHILD: 5

RIGHT CHILD: 7

ROOT: 5

ROOT: 7

The code I am using to print out the tree is,

boolean checkBST(Node root) { if(root!=null) { System.out.println("ROOT: " + root.data); if(root.left!=null) { System.out.println("LEFT CHILD: " + root.left.data); } if(root.right!=null) { System.out.println("RIGHT CHILD: " + root.right.data); } } if(root.left!=null) { checkBST(root.left); } if(root.right!=null) { checkBST(root.right); } return true; }

rajanbhandari09 + 1 comment My code should return a false for this tree...Are you getting a different result? If you traverse these nodes in In order you get 1->2->4->3->5->6->7 which is clearly not sorted as 4 is greater than 3.

j3ss0u + 0 comments [deleted]

TioTala + 0 comments Just a little improvement. As soon as flag is false we don't need to follow with the right tree.

Node* prevNode = NULL; bool inOrderTraversal(Node *node, bool flag) { if(node->left != NULL) { flag = inOrderTraversal(node->left, flag); } if(prevNode != NULL && prevNode->data >= node->data) { flag = false; } else { prevNode = node; if(node->right != NULL) { flag = inOrderTraversal(node->right, flag); } } return flag; } bool checkBST(Node *root) { bool flag = true; return inOrderTraversal(root,flag); }

With this little improvement pass all test cases as well

Regards

tina6397 + 0 comments Thanks!! made my day :)

bavadharani_m_21 + 0 comments can you explain this code

rjdp9736 + 2 comments whats is tree representation format in testcase?

mmkaps + 0 comments This is a in-order traversal. Left-root-Right. So, for 32 nodes, 16th node is the root. 1st node would be leftmost leaf child.

kutaykalkan + 0 comments You can check online for tutorials online. It is super simple.

lutando + 1 comment The problem states:

- The value of every node in a node's left subtree is less than the data value of that node.
- The value of every node in a node's right subtree is greater than the data value of that node.

however to pass the tests you have to check for less and equal to (

`<=`

), and grater than or equal to (`>=`

)mahmoud_alsayed1 + 0 comments [deleted]

omkar_ashrit + 0 comments I did an inorder traversal and check for increasing order. CODE:

vector<int> a; void in(Node* root) { if(root) { in(root->left); a.push_back(root->data); in(root->right); } } bool checkBST(Node* root) { in(root); for(int i = 0;i<a.size()-1;i++){ if(a[i]>=a[i+1]) return false; } return true; }

Sort 497 Discussions, By:

Please Login in order to post a comment