Verifying whether a tree is bst or not Python

Question

I have a practice interview question which tells me to verify if a tree is a balanced search tree or not and give a verification method... I have the class as

Class Node:
def __init__(self, k, val):
    self.key = k
    self.value = val
    self.left = None
    self.right = None

and other function definitions for the tree max and min values as

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

def tree_min(node):
    minleft  = float('-inf') if not node.right else tree_min(node.left)
    minright = float('-inf') if not node.left else tree_min(node.right)
    return min(node.value, minleft, minright)

My verification method as

def verify(node):
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right):
       if verify(node.left) and verify(node.right):
           return True
       else:
           return False
    else:
        return False

My problem occurs when I try to implement the verification method I seem to always get false even when I try to make a BST tree. My implementation is as follows:

root= Node(10, "Hello")
root.left = Node(15, "Fifteen")
root.right= Node(30, "Thirty")

print verify(root)

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print verify(root)

Both are giving me False...Is there a problem with my verification function or my min/max function...Any help would be appreciated.

Answer 1

I see four errors in your code.

1. First, your check for null children is backwards in tree_min. That is, you're checking if node.right exists before accessing node.left, and vise versa.

2. Second, tree.min returns negative infinity when called on a leaf node. You need to use positive infinity in the min calculation (negative infinity is correct in the max version).

3. Third, you have a logic error within verify, as it unconditionally calls tree_min or tree_max and itself on it's child nodes, even if one or both of them are None. I suggest making all the functions handle being passed None, rather than relying on the caller to do the right thing. This also simplifies the min and max code a bit!

4. Lastly, you're doing your comparisons on node.value, which is the string you're giving each node. I suspect you want to be comparing using node.key instead. Comparing a float (like float("-inf")) to a string (like "ten") is an error in Python 3, and even in Python 2 where it is legal, it probably doesn't work like you would expect.

With those issues fixed, I get expected results when I create valid and invalid trees. Your two examples are both invalid though, so if you were using them to test, you will always get a False result.

Finally, a couple of minor style issues (that aren't bugs, but still things that could be improved). Python supports chained comparisons, so you can simplify your first if statement in verify to tree_max(node.left) <= node.key <= tree_min(node.right). You can further simplify that part of the code by connecting the checks with and rather than nesting an additional if statement.

Here's a version of your code that works for me (using Python 3, though I think it is all backwards compatible to Python 2):

class Node:
    def __init__(self, k, val):
        self.key = k
        self.value = val
        self.left = None
        self.right = None

def tree_max(node):
    if not node:
        return float("-inf")
    maxleft  = tree_max(node.left)
    maxright = tree_max(node.right)
    return max(node.key, maxleft, maxright)

def tree_min(node):
    if not node:
        return float("inf")
    minleft  = tree_min(node.left)
    minright = tree_min(node.right)
    return min(node.key, minleft, minright)

def verify(node):
    if not node:
        return True
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and
        verify(node.left) and verify(node.right)):
        return True
    else:
        return False

root= Node(10, "Hello")
root.left = Node(5, "Five")
root.right= Node(30, "Thirty")

print(verify(root)) # prints True, since this tree is valid

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print(verify(root)) # prints False, since 15 is to the left of 10