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.

Source: codewars | Difficulty: EASY
Tags: Tree algorithms

Data structures

Complete search

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 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)