Preface

We are going to learn about a new data structure called Binary Search Tree (henceforth abbreviated as BST). We will use BST to implement the OrderedSet ADT and we claim this implementation can, potentially, be more efficient than the alternatives we have explored.

The intuition behind the new data structure is in creating non-linear linked nodes so we can perform binary search (with the expected efficiency, as in a sorted array) but also insert and remove efficiently (without shifting elements around as in a sorted array).

Go to the next lesson for explanation of the illustration above!