# Binary Search Tree

A binary search tree (BST) is a binary tree where each node has a comparable key (and an associated value) and
the tree is sorted on this key. The worst case scenario for searching and inserting is $O(N)$, if all the nodes
are on the left (or right). In the average case the cost is $O(1.39\log(N))$.

## Demo

A depth-first search method is used on the BST to create the image below. The example contains $N=1000$ values, which are sorted
when they are inserted into the tree. Refresh the page to create a new random tree.