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.
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(n2) --- 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))