Binary search tree

Binary search trees (BST) are variants of binary trees. They share most of the same characteristics of binary trees, except that leaves to the left of the node are less than the node’s value, and leaves to the right are greater than the node’s value.

What does this mean? The tree is ordered! So it’s easy to search. The leftmost node is is the smallest value and the rightmost node is the greatest, and the idea is that there cannot be any duplicate nodes.

Complexity

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)$. For a balanced tree, it has a worst-case complexity of $O(\log n)$, because we divide the search set in half each time.

In fact, the basic operations all have time complexities of $O(\log n)$.

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)!

typedef struct node {
	int data;
	struct node *right, *left;
} Node; // for binary search trees
 
typedef struct bstree {
	Node *root;
} BSTree; // for the root node of the tree

What differentiates binary search trees from regular trees is

Functions

For node creation:

Node *createNode(int value) {
	Node *newNode = (Node*)malloc(sizeof(Node)); // pointer to DMA node
	if (newNode != NULL) {
		newNode -> data = value;
		newNode -> right = newNode -> left = NULL;
	}
	return newNode;
}

For searching the tree. We can do this iteratively because it’s pretty easy to keep track of.

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

For inserting 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);
}

To print in ascending order of node values, we do the below. If we shuffle the order of the lines we can print in a different order.

void BSTree::printHelper(BSNode *n) {
	if (n == nullptr)
		return;
	printHelper(n->getLeft());
	cout << n->getValue();
	printHelper(n->getRight());
}
 
void BSTree::print() {
	return printHelper(root);
}

Addendum

Balanced binary search trees are popular because they guarantee our basic tree operations will have $O(\log n)$ even in the worst case scenario. Variants of this include:

• AVL tree
• Red-black tree

See also

• Binary search