Pace University Binary Search Tree Data Structures and Algorithms Report

The way that data is stored in a Binary Search Tree (BST) depends on
the order in which the values are inserted. For example, if we insert the
numbers 1; 2; 3 in that order, the resulting tree has 1 in the root, 2 as the
right child of 1, and 3 as the right child of 2. However, if we insert rst 2,
it will be stored in the root, and 1 and 3 will be its children. That is, not
only the values are stored in dierent nodes but also the shape of the tree
obtained is dierent. The rst one is skewed to the right whereas the second
one is balanced. As a consequence, although both trees contain the same
data, the worst-case cost of searching diers.
The purpose of this homework is to highlight this striking dierence in
running time, creating a skewed BST and a (roughly) balanced BST, both
with a large number of nodes, and measuring the worst-case execution time
of searching on each. To do that, we will assume that the order in which the
numbers are inserted is our choice, to produce the desired shape, and we will
search for a number that is not in the tree, to force the worst case. The BST
class needed for this assignment is attached. DO NOT MODIFY IT.