Check if a tree is a Binary Search Tree (BST)

Question

I am trying to solve a binary search tree problem, but I can't pass all of the test cases. I need to return true if the tree is a binary search tree, otherwise, I need to return false. Can anyone tell me what I am doing wrong?

'''
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
'''

def checkBST(root):
    if root.left == None and root.right == None:
        return True
    if root == None:
        return True
    if root.left != None:
        if root.left.data < root.data:
            return True
    else:
        return False
    if root.right != None:
        if root.right.data > root.data:
            return True
        else:
            return False
    return chckBST(root.left) and chckBST(root) and chckBST(root.right)

Answer 1

You've a lot of redundant if conditions in your code. You can simplify it like so:

def checkBST(root):
    if root == None or (root.left == None and root.right == None):
        return True

    elif root.right == None:
        return root.left.data < root.data and checkBST(root.left)

    elif root.left == None:
        return root.right.data >= root.data and checkBST(root.right)

    return checkBST(root.left) and checkBST(root.right)

First, check for all the None conditions. Short circuiting in python guarantees that if the first condition is False, the second will not be evaluated. This allows you to write succinct statements such as return root.left.data < root.data and checkBST(root.left).

Finally, in the event that neither left nor right nodes are None, do not call checkBST(root) again. This leads to infinite recursion.