Draw the sequence of BSTs that results when you insert the keys E, A, S, Y, Q, U, E, S, T, I, O, N, in that order into an initially empty tree. And draw the sequence of BSTs that results when you delete the keys from the tree one by one in the order they were inserted. (Note: here your BST should allow duplicate keys).

An important special kind of binary tree is the binary search tree (BST). In a BST, each node stores some information including a unique key value, and perhaps some associated data. A binary tree is a BST iff, for every node n in the tree:

All keys in n's left subtree are less than the key in n, and

all keys in n's right subtree are greater than the key in n.

Note: if duplicate keys are allowed, then nodes with values that are equal to the key in node n can be either in n's left subtree or in its right subtree (but not both). In these notes, we will assume that duplicates are not allowed.

Here are some BSTs in which each node just stores an integer key: