Binary Search Tree

A binary search tree is a special type of binary tree that follows an ordering property that enables it to be very efficient in standard operations in most cases.

Properties

The main property binary search trees have that distinguishes them from regular binary trees is that every node must be larger than all node values in its left subtree, and smaller than all node values in its right subtree.

As a consequence of this property, traversing a binary search tree in-order will always result in a non-decreasing order of node values.

Operations

Search

Searching in a BST is quite simple, and can be implemented with something like the following:

node* search(node* n, int value){
	if(n == nullptr) return nullptr;
	if(n->data == value) return n;
	
	if(n->data < value){ //this node is smaller than our target value,
		//therefore the node must be in the right subtree
		return search(n->right);
	} else { //otherwise it is either in the left subtree or it doesn't exist
		return search(n->left);
	}
}

Insertion

Inserting into a BST is also relatively simple. To preserve the ordered property of a BST, we must check that the node is inserted in the right spot. To do so, we can do something like the following:

void insert(node*& root, node* n){ // n new node
	if(n == nullptr) return;
	
	if(root == nullptr){
		root = n; //this wouldn't work if root wasn't pass by reference!
		return;
	}
	
	if(n->value < root->value){
		if(root->left == nullptr){
			root->left = n;
			return;
		}
		insert(root->left, n);
	}
	
	if(n->value > root->value){
		if(root->right == nullptr){
			root->right = n;
			return;
		}
		insert(root->right, n);
	}
	
	//lets say we have duplicates, in which case we can ignore duplicates
	if(n->value == root->value) return;
}

Deletion

Deletion is a bit more complicated, and has three subcases. A fully functioning deleteBST implementation would consider all of the following:

Leaf Node

If the node we’re deleting is a leaf node, easy, we just remove the leaf node and we assign null to its parents reference, and optionally free or delete it if it was dynamically allocated.

Single Child

If the node has a single child, we replace the node with its subtree directly. I.e., if it has a left child, the left child becomes the node itself.

Two Children

This case is a little bit more complex. If a node has two children, we need to find its predecessor, which is just the right-bottom-most node of the left subtree of a BST. We then replace the node we’re deleting with the predecessor.

We then delete the predecessor, which will fall under either the leaf node or single child case above.

Operation Complexity

If a binary tree is balanced, search, insertion and deletion are all

$$O(\log n)$$

However, this is only guaranteed to be the case in self-balancing binary trees like an AVL tree. In the case of the BST, there is an adversarial case where the binary search tree is effectively a linked list, a super-right (or super-left) heavy tree, where the worst case time complexity is then $O(n)$. This is the degenerate binary tree case, in this class also sometimes called a spine or stick.

This case is caused by repeatedly inserting nodes of increasing or decreasing values, like iteratively inserting elements of a sorted array.

Therefore, it is most accurate to say that the average case of operations in a BST is $O(\log n)$, but the worst case is $O(n)$.