# Trees: Is This a Binary Search Tree?

# Trees: Is This a Binary Search Tree?

jongray93 + 22 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 + 14 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?

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

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

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

sergeismth + 3 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!

Ghos3t + 0 comments in the following line of your code:

inorder_list = inorder(root)

won't inorder_list simply hold a reference to the original list_ so can't we just write the return statement like this-

return sorted(list(set(list_))) == list_

What is the use of the inoder_list variable in your code?

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 + 1 comment Guys will this work for if the BinaryTree has

**Duplicate Values**as said in the question, duplicate values are not allowed in BST?famibica + 0 comments 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.

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]techieme + 1 comment **Gives Error:**Solution.java:88: error: cannot find symbol System.out.println( (tree.checkBST(root)) ? "Yes" : "No" ); ^ symbol: method checkBST(Node) location: variable tree of type Tree 1 error

**Though Tree word/type is no where used in code.**oyebolaodukoya + 0 comments Did you figure the error out? I'm having the same problem

cpandey05 + 2 comments Trying to submit similar code but getting this error Compiler Message

Runtime Error

Error (stderr)

`Error: Could not find or load main class Solution`

abhipsa_mohapat1 + 1 comment did u find a solution

Karamjit + 0 comments no****

godwinwoo + 0 comments Test case 3,6,7 fail with this solution in Python. Why?

Karamjit + 0 comments this code is givving me runtime error

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

StuckAndSteaming + 16 comments Anybody else getting this error? (on java)

Error: Could not find or load main class Solution

I thought we only had to fill out the function?

rockydgeekgod + 0 comments Yes, I am getting same error.

hsznav + 0 comments same here :(

diemto92 + 0 comments Same for me :(

jteich3 + 0 comments Yup, it appears to be broken :(

catherineluse + 0 comments Same problem.

codeanit + 0 comments Hint: Inner Class.

Also I think there is some issue with the question at run time. Some times it passes sometimes it fails during submission with the same set of code. @saikiran9194

nindyahapsari + 0 comments I had the same problems..sometimes it works and it will come back to runtime error

soagra0520 + 0 comments I'm also getting the same error over and over.

dxlxd + 1 comment Was this ever resolved?

madhu131313 + 0 comments I tooo am facing the same issue

radistao + 0 comments same here (( shall we report? do they actually answer? i reported one broken test input, bun there is no any answer ((

triples360 + 0 comments [deleted]lightinzide + 0 comments i do

chrissimcik + 1 comment me too ??

annu_mait + 0 comments me too :(

alexvlsem + 0 comments Same for me :(

akashtripathi93 + 0 comments I am also getting the same error.

yabets_s_belay + 0 comments I am also getting the same. Any solution

omarmohssen + 0 comments for Java the hidden code seems to have issues ? if I test the function by just returning a simple true, I get:

Error: Could not find or load main class Solution

I tried to wrap the function with the class but still didn't work, any suggestion ?

windmsh + 2 comments I am running into :

Runtime Error

Error: Could not find or load main class Solution

I think the issue is that I don't have the helper main class.

Anyone else ran into this issue ?

Thanks

wjs2700 + 0 comments I think they are not qualified to test anybody until they perfect itself's dreadful platform .

Sort 637 Discussions, By:

Please Login in order to post a comment