If we write our binary tree nodes as triples (left subtree, node, right subtree), and the null pointer as None, we can build and search them as follows (in Python):

def binary_tree_insert(treenode, value):if treenode is None: return (None, value, None) left, nodevalue, right = treenode if nodevalue > value: return (binary_tree_insert(left, value), nodevalue, right) else: return (left, nodevalue, binary_tree_insert(right, value))def build_binary_tree(values):

tree = None for v in values: tree = binary_tree_insert(tree, v) return treedef search_binary_tree(treenode, value):

if treenode is None: return None # failure left, nodevalue, right = treenode if nodevalue > value: return search_binary_tree(left, value) elif value > nodevalue: return search_binary_tree(right, value) else: return nodevalue

Note that the worst case of this `build_binary_tree` routine is O(*n*^{2}) --- if you feed it a sorted list of values, it chains them into a linked list with no left subtrees. For example, `build_binary_tree`([1, 2, 3, 4, 5]) yields the tree (None, 1, (None, 2, (None, 3, (None, 4, (None, 5, None))))). There are a variety of schemes for overcoming this flaw with simple binary trees.

Once we have a binary tree in this form, a simple inorder traversal can give us the node values in sorted order:

def traverse_binary_tree(treenode):if treenode is None: return [] else: left, value, right = treenode return (traverse_binary_tree(left) + [value] + traverse_binary_tree(right))

So the binary tree sort algorithm is just the following:

def treesort(array):array[:] = traverse_binary_tree(build_binary_tree(array))

There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees. A B-tree grows from the bottom up as elements are inserted. A splay tree is a self-adjusting binary search tree. In a treap ("tree heap"), each node also holds a priority and the parent node has higher priority than its children.