Binary search tree

Binary search trees (BST) are variants of binary trees. They share the same characteristics of binary trees, except that they have an additional property. For a given node $v$, all nodes in the left subtree have keys less than $v$, and all nodes in the right subtree have keys greater than $v$.

The implication: the tree is ordered and easy to search. The leftmost node is the smallest value, and the rightmost is the greatest. We also restrict the tree from containing any duplicate nodes. Because most operations of BSTs take $O(\log n)$ time, they make an ideal data structure to apply and extend on. Important variations of BSTs include:

• Red-black tree
• AVL tree

Operations and complexity

Binary trees have a space complexity of $O(n)$, since they store all elements. Thus, any walks that visit all nodes (in-order, post-order, pre-order) will have a time complexity of $\Theta (n)$.

Querying a tree takes less operations than a regular binary tree, because of the key BST property. For a balanced tree, it has a worst-case complexity of $O(\log n)$, because we divide the search set in half each time. If the tree is unbalanced (i.e., it looks like a linked list), then to search has a worst-case time complexity of $O(n)$.

To delete a node, we have three cases:

• No children — simple deletion. No need to do anything else.
• One child — set the root key as the child key, and delete the child.
• Two children — most complicated. Take the minimum value of the right subtree as the new root. To fix up the tree,

More complicated complexity

If we do two operations at once, like recursively printing out the tree, then we run into $O(2^{\log n})$, because of the two operations and because we cut the search set each time. This in fact reduces down to $O(n)$ (via some funky algebra)!

Implementation

Most languages will implement a binary tree as follows:

struct Node {
	int key;
	Node *right, *left;
}
 
struct Tree {
	Node *root;
}

The search function can be done both recursively and iteratively.

Node *search (Tree *tree, int key) {
	Node *current = tree -> root;
	while (current != nullptr and current -> data != key) {
		if (current -> data < key) {
			current = current -> right;
		} else if (current -> data > key) {
			current = current -> left;
		}
	}
	return nullptr;
}

To insert a node:

void BSTree::insertHelper(int v, BSTNode *n) { // helper functions can be private
	if (n->getValue() == v)
		return;
	if (n->getValue() > v) {
		if (n->getLeft() == nullptr) {
			n->setLeft(new BSTNode(v));
		} else {
			return insertHelper(v, n->getLeft());
		}
	} else if (n->getValue() < v) {
		if (n->getRight() == nullptr) {
			n->setRight(new BSTNode(v));
		} else
			return insertHelper(v, n->getRight());
	}
}
 
void BSTree::insert(int v) { // actual function can be public
	if (root == nullptr)
		root = new BSTNode(v);
	else
		insertHelper(v, root);
}

See also

• Binary search