Exercise: Scapegoat Trees

Task

Modify the add(x) method for ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).

Sample input

The sample input will be as follows:

5
3
8
1
4
7
9

Expected output

The expected output will be as follows:

Tree contents:
1 3 4 5 7 8 9 
Tree after removing 4:
1 3 5 7 8 9