Binary search tree

A binary search tree is a binary tree where in each node:

• The left subtree contains only nodes with keys less than the node's key (the "data"/"value" of the node).
• The right subtree contains only nodes with keys greater than the node's key.
• Both subtrees are also binary search trees.

It follows that each key is distinct.

Binary search trees are especially useful in constructing other data structures such as sets, multisets and associative arrays.

Operations

Searching

Searching a binary search tree can easily be done using either an iterative or recursive method. Starting with the root node, we check to see if the current node contains the key we are searching for. If yes, then the key is found. If not, we do the search on the left subtree if the key is less, or the right subtree if the key is greater. We end the search when there is no existing child corresponding to the key (hence no subtree).

Recursive

This is a recursive algorithm for returning the value of a generic associative array implementation of a binary search tree, where valuetype is the type of the values. The type of the key is a comparable type where the operators <, > and = are defined.

search(key) as valuetype
    return search(root, key)

search(node, key) as valuetype
    if node is null then
        return null
    if key < node.key then
        return search(code.leftchild, key)
    else if key > node.key then
        return search(node.rightchild, key)
    else // equal
        return false.value

Iterative

search_iterative(key) as valuetype
    return search_iterative(root, key)

search_iterative(node, key) as valuetype
    currentnode = node
    while node is not null
         if key < node.key then
             node = node.leftchild
         else if key > node.key then
             node = node.rightchild
         else // equal
             return node.value
    return false // exited while loop, null child

Insertion

As with searching, we find a location where we would insert the new node. This is done recursively until we find a free node where we could insert the new node.

Recursive

insert(key, value)
    insert(root, key, value)

insert(ref node, key, value)
    if node is null
        node = new node with key = key, value = value
    else if key < node.key
        insert(node.leftchild, key, value)
    else if key > node.key
        insert(node.rightchild, key, value)
    else
        throw new exception with message = "key already exists in tree"

Recursive, without references

insert(node, key, value)
    if key < node.key
        if node.leftchild is null then
            node.leftchild = new node with key = key, value = value
        else
            insert(node.leftchild, key, value)
    else if key > node.key
        if node.rightchild is null then
            node.rightchild = new node with key = key, value = value
    else
        throw new exception with message = "key already exists in tree"

Traversal

We can use an inorder traversal to traverse through the nodes in the tree in order (of the keys).

Algorithm (recursive)

traverse() as list of node
    return traverse(root)

traverse(node) as list of node
    list = new list of node
    list.add(traverse(node.leftchild))
    list.add(node)
    list.add(traverse(node.rightchild))
    return list

Sorting

A binary search tree can be used to implement a simple sorting algorithm.

Algorithm

sort(list of t) as list of t
    tree = new binarysearchtree(t, t)
    for each item in list
        tree.insert(item, null)
    return keys in tree.traverse