A **binary search tree** is a binary tree where every node has a value, every node's left subtree has values less than the node's value, and every right subtree has values greater. A new node is added as a leaf. There is a sort algorithm based on binary search trees, and also a search algorithm.

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

See also: AVL tree, Red-Black tree, splay tree, treap?