# Binary search tree

*406*pages on

this wiki

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.

## OperationsEdit

### SearchingEdit

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

### InsertionEdit

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"

### TraversalEdit

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

### SortingEdit

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