Binary Search Trees
A Binary Search Tree (BST) is a binary tree where the nodes are ordered following these characteristics:
- The left subtree of a node contains only nodes with values lower than the node’s value
- The right subtree of a node contains only nodes with values greater than the node’s value
- The left and right subtree each must also be a Binary Search Tree
- There must be no duplicate values
- A unique path exists from the root to every other node
The possible operations on a Binary Search Tree are: Search, Insert and Delete. An update is just a delete followed by an insert.
Binary Search Trees are pretty easy to implement and let you insert, delete and search in O(n) in the worse case scenario. There are self-balancing Binary Search Trees, that are harder to implement but offer O(log n) performance. I’m not going to cover self-balancing trees in this post.