Check is a tree in python is a Binary Search tree

Question

I want to write a function that shows me if a given tree is BinarySearch or not.

This is what I wrote so far:

class Node: 

     def _isBinary(self):
        
        L=[]

        if self.left is not None and self.right is not None:
            if self.left.data>self.data or self.right.data<self.data:
               L.append(1)
            else:
               L+=self.left._isBinary()
               L+=self.right._isBinary()
        else:

            if self.left is not None:
               if self.left.data>self.datat:
                  L.append(1)
               else:
                  self.left._isBinary()

            if self.right is not None:
               if self.right.data<self.data:
                  L.append(1)
               else:
                  self.right._isBinary()

       return L

class tree:
    
    def isBinary(self):
        if self.root is None:
            return
        else:
            return  not 1 in self.root._isBinary(self.root.data)

(obisivuly I just reported the interested part of the code) This code works finely, but gives me the incorrect answer when, for example, a number (bigger than the root) is in the left side of the tree, but is the children of a lower number:

     99
    /  \
   8   888
    \
     100

It should give me False, instead it returns True. What can I do? (if possible, without changing completely my original code?)

Answer 1

A different approach would be to just do an inorder traversal of the BST then check if it is sorted. Inorder traversal of an BST is sorted.

def inorder(node):
    if node is None:
        return
    yield from inorder(node.left)
    yield node.data
    yield from inorder(node.right)


inorder_traversal = list(inorder(root))
print(all(i<=j for i, j in zip(inorder_traversal, inorder_traversal[1:]))) # check if sorted

You can bring in itertools.tee to gain better performance due to the short circuiting nature of all.

inorder_traversal = inorder(root)
a, b = tee(inorder_traversal) # copy the `inorder_traversal` iterator
next(b) # discard first element
print(all(i<=j for i, j in zip(a,b))) # check if sorted

For more information on how tee works you can refer to this answer Iterate a list as pair (current, next) in Python.

Answer 2

Some approach along the following lines should work:

class Node:
    def is_binary_search(self, lo=None, hi=None):
        if lo is not None and lo > self.data:
            return False
        if hi is not None and hi < self.data:
            return False
        if self.left and not self.left.is_binary_search(lo=lo, hi=self.data):
            return False
        if self.right and not self.right.is_binary_search(lo=self.data, hi=hi):
            return False
        return True

You pass those subtree boundaries that are already known (lo and hi) down the recursive calls.

Answer 3

You can traverse your tree in sequential order and check that the values are ascending. Using an iterator will avoid the need to create any lists.

def iter(self):
    if self.left:  yield from self.left.iter()
    yield self
    if self.right: yield from self.right.iter()

from itertools import islice
def isBinary(self):
    return all(a<b for a,b in zip(self.iter(),islice(self.iter(),1,None)))

    
     

Answer 4

Assuming that a node is defined like that

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

This simple recursive function should be sufficient. Passing two different comparator functions for the left and right subtrees as a callable argument to the inner recursive function. Not the shortest possible solution, but doesn't look like black magic (hopefully).

def is_bst(root):
    def is_bst_recursive(node, in_order):
        if node is None:
            return True
        if not in_order(node.value):
            return False
        if node.left and node.left.value >= node.value:
            return False
        if node.right and node.right.value <= node.value:
            return False
        return (is_bst_recursive(node.left, in_order)
                and is_bst_recursive(node.right, in_order))

    return (is_bst_recursive(root.left, lambda x: x < root.value)
            and is_bst_recursive(root.right, lambda x: x > root.value))

Answer 5

We can write is_binary_search which takes an input tree, t, and a compare function which defaults to always True -

def is_binary_search(t, compare = lambda _: True):
  if not t:
    return True
  else:
    return compare(t.data) \
       and is_binary_search(t.left, lambda l: compare(l) and l < t.data) \
       and is_binary_search(t.right, lambda r: compare(r) and r > t.data)

We create two trees to test our function -

• t1, an invalid binary search tree, provided in your example question
• t2, a valid binary search tree

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

t1 = \
  node(99, node(8, None, node(100)), node(888))

#    99
#   /  \
#  8   888
#   \
#    100


t2 = \
  node(99, node(8, None, node(10)), node(888))

#    99
#   /  \
#  8   888
#   \
#    10

print(is_binary_search(t1)) # False
print(is_binary_search(t2)) # True

We should also test cases like an empty tree, None, and a tree of just a single node, each of which are valid binary search trees -

print(is_binary_search(None)) # True
print(is_binary_search(node(123))) # True