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

  • 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

              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

              • 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 + 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?