A [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) is a binary tree that is ordered. This means that if you were to convert the tree to an array using an in-order traversal, the array would be in sorted order. The benefit gained by this ordering is that when the tree is balanced, searching is a logarithmic time operation, since each node you look at that isn't the one you're searching for lets you discard half of the tree.

If you haven't worked with binary trees before or don't understand what a traversal is, you can learn more about that here: https://www.codewars.com/kata/binary-tree-traversal.

In this kata, you will write a function that will validate that a given binary tree is a binary search tree. The sort order is not predefined so it should work with either.

These are valid binary search trees:

        5
       / \
      2   7
     / \   \
    1   3   9


      7
     / \
    9   2


while these are not:

      1
     / \
    2   3


      5
     / \
    2   9
     \
      7

There are several different approaches you can take to solve this kata. If you're not as comfortable with recursion I'd recommend practicing that.

Note: no test case tree will contain duplicate numbers.

Difficulty: introductory

Starter code:

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

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


def is_bst(node):

    def extract(node):
        if node is not None:
            yield from extract(node.left)
            yield node.value
            yield from extract(node.right)
    
    gen = extract(node)
    try:
        u, v = next(gen), next(gen)
    except StopIteration:
        return True
    
    cmp = u<v
    for w in gen:
        if cmp != (v<w): return False
        v = w
    return True

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


def walk_tree(node):
    if node is None:
        return []
    
    return walk_tree(node.left) + [node.value] + walk_tree(node.right)


def is_bst(node):
    vals = walk_tree(node)
    ordered = vals[:]
    ordered.sort()
    return (ordered == vals) or (ordered == vals[::-1])


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

def is_bst(node):
    def walk(node, from_, to_, min_=float('-inf'), max_=float('inf')):
        return node is None or min_ <= node.value <= max_ \
            and walk(getattr(node, from_), from_, to_, min_, node.value) \
            and walk(getattr(node, to_  ), from_, to_, node.value, max_)
    return walk(node, 'left', 'right') or walk(node, 'right', 'left')

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

def preorder(self):
    if not self:
        return []
    return [self.value] + preorder(self.left) + preorder(self.right)

def is_bst(T):
    if not (T and (T.left or T.right)):
        return True
    v, l, r, R1, R2 = T.value, T.left, T.right, True, True
    if l and max(preorder(l)) > v or r and min(preorder(r)) < v:
        R1 = False
    if l and min(preorder(l)) < v or r and max(preorder(r)) > v:
        R2 = False
    return is_bst(l) and is_bst(r) and (R1 or R2)

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

def inorder(self):
    if not self:
        return []
    return inorder(self.left) + [self.value] + inorder(self.right)

def is_bst(node):
    curr=inorder(node)
    return sorted(curr) in (curr, curr[::-1])

class T:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        
def is_bst(node):
    to_arr = lambda t: to_arr(t.left) + [t.value] + to_arr(t.right) if t else []
    arr = to_arr(node)
    s = sorted(arr)
    return s == arr or s == arr[::-1]

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

def is_bst(node):
    def traverse(n):
        return [] if not n else traverse(n.left) + [n.value] + traverse(n.right)
    vals = traverse(node)
    zipped = list(zip(vals, vals[1:]))
    return all(a < b for a, b in zipped) or all(a > b for a, b in zipped)

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

def inorder(self):
    if not self:
        return []
    return inorder(self.left) + [self.value] + inorder(self.right)

def is_bst(T):
    io = inorder(T)
    return sorted(io) in (io, io[::-1])

class T:
    def __init__(self,value,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right
        
def levelorder(self):
    if not self:
        return []
    queue, R = [self], [self.value]
    while queue:
        Next = queue.pop(0)
        for T in [Next.left, Next.right]:
            if T:
                queue.append(T)
                R.append(T.value)
    return R

def is_bst1(T):
    if not (T and (T.left or T.right)):
        return True
    v, l, r = T.value, T.left, T.right
    if l and max(levelorder(l)) > v or r and min(levelorder(r)) < v:
        return False
    return is_bst1(l) and is_bst1(r)

def is_bst2(T):
    if not (T and (T.left or T.right)):
        return True
    v, l, r = T.value, T.left, T.right
    if l and min(levelorder(l)) < v or r and max(levelorder(r)) > v:
        return False
    return is_bst2(l) and is_bst2(r)

def is_bst(T):
    return is_bst1(T) or is_bst2(T)

from operator import gt, lt


def max_child(root):
    max_val = root.value
    if root.left is not None:
        max_left = max_child(root.left)
        max_val = max(max_val, max_left)
    if root.right is not None:
        max_right = max_child(root.right)
        max_val = max(max_val, max_right)
    return max_val


def min_child(root):
    min_val = root.value
    if root.left is not None:
        min_left = min_child(root.left)
        min_val = min(min_val, min_left)
    if root.right is not None:
        min_right = min_child(root.right)
        min_val = min(min_val, min_right)
    return min_val


comparator_mapper = {
    gt: max_child,
    lt: min_child
}


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


def is_bst(node):
    if node is None:
        return True
    if node.left is not None and node.left.value > node.value or node.right is not None and node.right.value < node.value:
        return validate(node, lt, gt)

    return validate(node, gt, lt)


def validate(root, left_tree_compare, right_tree_compare):
    if root is None:
        return True

    return (left_tree_compare(root.value,
                              comparator_mapper[left_tree_compare](root.left)) if root.left is not None else True) and (
               right_tree_compare(root.value, comparator_mapper[right_tree_compare](
                   root.right)) if root.right is not None else True) and validate(
        root.left, left_tree_compare, right_tree_compare) and validate(root.right, left_tree_compare,
                                                                       right_tree_compare)