=============================================================================
       CSC 263                Tutorial 3               Winter 2019
=============================================================================

Suppose we want to use a Binary Search Tree to store only keys (without any
additional information), and we want to allow duplicate keys. For example, if
we insert the key 12 twice, the BST should behave exactly as if there were
two separate copies of the key 12 stored in the tree.


 1. The algorithm that we covered in lecture for TreeInsert does not handle
    this situation right now: it explicitly disallows duplicate keys. Modify
    the TreeInsert algorithm from lecture so that duplicate keys can be
    inserted: treat equal keys the same way as larger keys (or smaller keys
    -- just pick one and use it consistently, to keep the algorithm simple).

    Write the complete algorithm and point out the changes you made. (Yes,
    this involves mostly copy-and-pasting the algorithm from class and making
    small changes -- it is meant to make you write down the complete
    algorithm and understand it, as preparation for the later questions.)

    Then, give a careful worst-case analysis of the running time of your
    algorithm when it is used to insert n identical keys into a BST that is
    initially empty.

    This is a little different from what we've done up until now: we don't
    want you to analyse the complexity of just one TreeInsert operation;
    we want you to analyse the *total* time taken by *all* n calls to
    TreeInsert.


In the rest of this tutorial, you will explore different ways that you can
improve on the running time of TreeInsert when duplicate keys are allowed.


 2. First strategy: ensure duplicate keys are not always inserted on the same
    side. Store a boolean flag goLeft in each node, initially set to True.
    During insertion, when the key to be inserted is equal to the current
    node's key, use the value of the current node's goLeft to determine
    whether to insert the key in the left subtree or in the right subtree,
    and flip the value of the current node's goLeft.

    Write the complete algorithm and point out changes from your answer to
    question 1.

    Then, give a careful worst-case analysis of the running time of your
    algorithm when it is used to insert n identical keys into a BST that is
    initially empty. As before, analyse the *total* time taken by *all* n
    calls to TreeInsert.


 3. Second strategy: during insertion, when the key to be inserted is equal
    to the current node's key, determine whether to insert in the left
    subtree or the right subtree at random -- with equal probabilities for
    left and right.

    Write the complete algorithm and point out changes from your answer to
    question 1. Then, analyse the worst-case performance of your algorithm
    when it is used to insert n identical keys into a BST that is initially
    empty, as before (this should be quick).

    Finally, give an informal analysis of the expected running time of your
    algorithm.


 4. Can you come up with a better strategy? There are at least two simple
    ideas that will work better for the particular case we are considering
    (inserting n identical keys in an initially empty BST).

    Describe your strategy in one concise paragraph, then write the complete
    algorithm (point out changes from previous parts) and give a careful
    worst-case analysis of your algorithm when it is used to insert n
    identical keys into a BST that is initially empty (as before).