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.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

    You are viewing a single comment's thread. Return to all comments →

  • jongray93 3 years ago+ 19 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);
    }
    
    107|
    Permalink
    • robertram 3 years ago+ 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);
          }
      
      23|
      ParentPermalink
      • LegendOri 3 years ago+ 2 comments

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

        3|
        ParentPermalink
        • gomorycut 3 years ago+ 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.

          7|
          ParentPermalink
          • mitap94 3 years ago+ 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

            1|
            ParentPermalink
            • susthan18 3 years ago+ 1 comment

              I am also facing the same issue, did you figure out the problem already?

              0|
              ParentPermalink
              • mike97 3 years ago+ 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.

                61|
                ParentPermalink
                • mitap94 3 years ago+ 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

                  1|
                  ParentPermalink
                  • d_liu1995 3 years ago+ 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.

                    6|
                    ParentPermalink
                • KSK1919 2 years ago+ 0 comments

                  thank you.really the best explanation.

                  0|
                  ParentPermalink
                • nmagee 2 years ago+ 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.

                  1|
                  ParentPermalink
                • anicse0904071 2 years ago+ 0 comments

                  cool

                  0|
                  ParentPermalink
                • hykavitha 2 years ago+ 0 comments

                  correct, and I have my solution that way. When debugging I realized it.

                  0|
                  ParentPermalink
                • skrm78 12 months ago+ 0 comments

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

                  0|
                  ParentPermalink
        • feng_xingxu 2 years ago+ 0 comments

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

          0|
          ParentPermalink
      • dasilvacontin 3 years ago+ 0 comments

        Thanks for pointing this out! :)

        1|
        ParentPermalink
      • leves 3 years ago+ 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.

        3|
        ParentPermalink
      • santosh984970 3 years ago+ 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

        0|
        ParentPermalink
        • debasishjrt 3 years ago+ 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.

          1|
          ParentPermalink
          • JustinMend 2 years ago+ 0 comments
            [deleted]
            0|
            ParentPermalink
      • madhukumari87 3 years ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
      • thirumla14116 2 years ago+ 0 comments

        thank you so much i understood far better than i actually should have a great day!!

        0|
        ParentPermalink
      • abhi47shrivasta1 2 years ago+ 0 comments

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

        0|
        ParentPermalink
      • rnatesan21 2 years ago+ 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?

        0|
        ParentPermalink
      • ritianfitchett 2 years ago+ 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.

        1|
        ParentPermalink
        • pranzy95 2 years ago+ 1 comment

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

          -1|
          ParentPermalink
          • ritianfitchett 2 years ago+ 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".

            1|
            ParentPermalink
      • BurBes 2 years ago+ 0 comments

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

        0|
        ParentPermalink
      • craigjbennetts 1 year ago+ 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?

        0|
        ParentPermalink
        • craigjbennetts 1 year ago+ 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'.

          0|
          ParentPermalink
      • abafna 1 year ago+ 0 comments

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

        1|
        ParentPermalink
      • faisalbhagat 1 year ago+ 0 comments

        will this code fail if tree has more than two layers?

        0|
        ParentPermalink
      • michellerodri247 2 months ago+ 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.

        0|
        ParentPermalink
    • ysndar 3 years ago+ 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.

      0|
      ParentPermalink
      • jongray93 3 years ago+ 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.

        5|
        ParentPermalink
        • umangthusu 3 years ago+ 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?

          1|
          ParentPermalink
          • Jstorm99 3 years ago+ 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);
                }
            
            9|
            ParentPermalink
            • wowlad 3 years ago+ 2 comments

              can u post an explanation,cant make out your logic

              0|
              ParentPermalink
              • Jstorm99 3 years ago+ 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

                image 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

                24|
                ParentPermalink
                • witygass 3 years ago+ 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
                  
                  1|
                  ParentPermalink
                  • eileen_duffner 3 years ago+ 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.

                    0|
                    ParentPermalink
                    • atb27 2 years ago+ 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

                      1|
                      ParentPermalink
                      • witygass 2 years ago+ 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.

                        0|
                        ParentPermalink
                        • Fantoxicated 2 years ago+ 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
                          
                          0|
                          ParentPermalink
                    • Dan_Golding 2 years ago+ 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
                      
                      4|
                      ParentPermalink
                      • svdubl 2 years ago+ 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)
                        
                        0|
                        ParentPermalink
                  • abieleck 5 months ago+ 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 :)

                    0|
                    ParentPermalink
                • sergeismth 2 years ago+ 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
                  
                  3|
                  ParentPermalink
                  • randyjp125 2 years ago+ 0 comments

                    Loved how you turned the list into a set to filter duplicates.

                    0|
                    ParentPermalink
                  • alex_vanoene 2 years ago+ 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!

                    0|
                    ParentPermalink
              • sayanarijit 2 years ago+ 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?

                0|
                ParentPermalink
                • kevinpaulboucher 2 years ago+ 0 comments
                  [deleted]
                  0|
                  ParentPermalink
                • ChrisGBloom 2 years ago+ 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

                  7|
                  ParentPermalink
                  • tutu_p 1 year ago+ 0 comments

                    Thx I was missing this!

                    0|
                    ParentPermalink
            • tvolkov 3 years ago+ 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

              0|
              ParentPermalink
              • munishpratap55 2 years ago+ 1 comment

                how?

                0|
                ParentPermalink
                • ChrisGBloom 2 years ago+ 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.

                  1|
                  ParentPermalink
              • patrick54 2 years ago+ 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.

                4|
                ParentPermalink
            • samr2 3 years ago+ 0 comments

              Beautiful!

              0|
              ParentPermalink
            • piyush_kr0707 3 years ago+ 0 comments
              [deleted]
              0|
              ParentPermalink
            • sattujaiswal 2 years ago+ 0 comments

              same :)

              0|
              ParentPermalink
            • jessebrowne 12 months ago+ 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.

              0|
              ParentPermalink
        • ysndar 3 years ago+ 0 comments

          Thanks :)

          0|
          ParentPermalink
      • ju7847 3 years ago+ 0 comments

        same here. what did you do?

        0|
        ParentPermalink
    • TheWicked 3 years ago+ 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.

      2|
      ParentPermalink
      • alkamid 3 years ago+ 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.

        0|
        ParentPermalink
    • andrerpena 3 years ago+ 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'))
      
      7|
      ParentPermalink
      • runcy 3 years ago+ 1 comment

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

        1|
        ParentPermalink
        • jcleyton 2 years ago+ 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.

          11|
          ParentPermalink
      • shalinikumar 3 years ago+ 1 comment

        Can you explain what is float('-inf')

        0|
        ParentPermalink
        • preyescar 3 years ago+ 0 comments

          negative infinity and positive infinity

          3|
          ParentPermalink
      • valtheval 3 years ago+ 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)
        
        0|
        ParentPermalink
        • condrint 2 years ago+ 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.'

          1|
          ParentPermalink
        • mindofmateo 2 years ago+ 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.

          0|
          ParentPermalink
      • Slaunger 2 years ago+ 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
        
        18|
        ParentPermalink
        • mindofmateo 2 years ago+ 0 comments

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

          2|
          ParentPermalink
        • kbenriquez 2 years ago+ 1 comment

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

          0|
          ParentPermalink
          • rich_vanbergen 1 year ago+ 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.

            0|
            ParentPermalink
            • budzinsa 1 year ago+ 0 comments

              This dynamic programming allows to skip reqursion, which is high performance gain.

              1|
              ParentPermalink
      • maheshksh 1 year ago+ 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)

        0|
        ParentPermalink
      • marklawstudio 1 year ago+ 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)

        0|
        ParentPermalink
    • saumyaj92 3 years ago+ 1 comment

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

      0|
      ParentPermalink
      • annguyen230693 3 years ago+ 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)

        1|
        ParentPermalink
    • Spiznak 2 years ago+ 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).

      2|
      ParentPermalink
      • Ippo343 2 years ago+ 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.

        2|
        ParentPermalink
    • sethdemasi 2 years ago+ 0 comments

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

      0|
      ParentPermalink
    • sakpal 2 years ago+ 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?

      0|
      ParentPermalink
      • famibica 3 months ago+ 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.

        0|
        ParentPermalink
    • bavadharani_m_21 2 years ago+ 0 comments

      can you explain this code

      0|
      ParentPermalink
    • Jeff_Chung123 2 years ago+ 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);

        }
        ```
      
      0|
      ParentPermalink
    • RGrazini 2 years ago+ 0 comments

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

      0|
      ParentPermalink
    • as6485v2 2 years ago+ 0 comments

      High five for sheer elegance!

      0|
      ParentPermalink
    • iamanshulkabra 2 years ago+ 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?

      2|
      ParentPermalink
    • msonde 2 years ago+ 0 comments

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

      1|
      ParentPermalink
    • nakar_tamir 2 years ago+ 0 comments

      Really nice one!

      0|
      ParentPermalink
    • GhostlyMowgli 1 year ago+ 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.

      0|
      ParentPermalink
    • alxnam 1 year ago+ 0 comments

      Is <=, >= enough to avoid duplicates in tree?

      0|
      ParentPermalink
    • wjbodyv 1 year ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • techieme 4 days ago+ 0 comments

      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.

      0|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature