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))
There are many types of binary search trees. AVL trees and RedBlack trees are both forms of balanced binary search trees. A Btree grows from the bottom up as elements are inserted. A splay tree is a selfadjusting binary search tree. In a treap ("tree heap"), each node also holds a priority and the parent node has higher priority than its children.
Search Encyclopedia

Featured Article
