RE: Midterm exam #

Oct 26, 7p-8:15p

Make sure to join using SSO.

One question at a time, can’t go back. Open notes, open book.

Binary search tree cont. #

Solutions for last exercises

This is invalid

This is valid

This is valid

Best case runtime is O(1). Worst case runtime is O(n).

Best case space complexity is O(1). Worst case space complexity is O(n).

Best case runtime for put method is O(1). Worst case runtime for put method is O(n).

Best case spacetime for put is O(1). Worst case spacetime for put is O(n).

The minimum key is as far left as possible.

public Key max()
{
    if (root) return null;
    else return max(root).key;
}

private Node max(Node node)
{
    if (node.right) return node;
    else return max(node.right);
}

public int height()
{
    if (root) return 0;
    else return height(root);
}

private int height(Node node)
{
    int leftSize);
    int rightSize);
    if (leftSize > rightSize)
    {
        // hmm
    }
}