HackerRank: Check Binary Search Tree: Python -test case -for duplications

Question

The question related to HackerRAank -"Trees: Is This a Binary Search Tree?"https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/problem

Challange is to check if a giving tree is a binary search tree Conditions: data in the left node will be smaller than root, data in the right node will be larger, values cannot be equal to the root. Tree cannot contain duplications Code:

def check( root, min_number ,max_number):
    if root == None or (root.left == None and root.right == None): #Check empty tree
        return True
    elif root.data <= root.left.data or root.right.data <= root.data: #+Check dup
        return False
    elif root.data <= int(min_number) or root.data >= int(max_number):
        return False
    elif root.right == None:
        return root.left.data < root.data and check(root.left)
    elif root.left == None:
         return root.right.data > root.data and check(root.right)
    else:
        return check(root.left, int(min_number), root.data) and check(root.right, root.data, int(max_number))

def checkBST(root):
    return check(root,0,10000)# const given

Not all duplications are caught.

Test case (this is only an example):

2
1 2 3 4 6 8 10 11 12 13 14 15 16 16 18 19 21 21 22 23 24 25 26 27 78

Answer should be No

Any suggestion of which condition I missed I missed /what needs to be adjusted?

aghast aghast · Accepted Answer · 2017-10-09T16:53:04

I think you're doing too much, and at the same time doing too little. Consider this fragment:

elif root.data <= root.left.data or root.right.data <= root.data: #+Check dup
    return False

Now consider this one:

else:
    return check(root.left, int(min_number), root.data) and check(root.right, root.data, int(max_number))

If you're going to recurse, in the second fragment, then why do you need to bother "reaching down" into the children for the comparisons in the first fragment?

Also, why do you occasionally try converting your numbers to int? Aren't you satisfied that they are integers to begin with?

I'll suggest that you reduce the amount of code - get rid of the int() coercions that are not needed, and get rid of tests that are redundant. Instead, focus only on the current node. Finally, make a choice- are you using <= and >= or < and > comparisons? Do that for all your tests, and make sure you adjust your parameters appropriately. If your incoming min and max values are inclusive parameters, then use <= and >=, and make sure you add or subtract one when you recurse.

HackerRank: Check Binary Search Tree: Python -test case -for duplications

1 Answers