ImmutableTrees

Note to plugin users: There is an image in this problem statement. Please use the applet to view it.

An insertion into an immutable binary search tree does not alter the existing tree. Rather, it creates a new tree that contains the new value. For example, if a tree contains the values 1, 2, and 3, and you insert the value 4, then the new tree contains the values 1, 2, 3, and 4, but the old tree still exists and still contains only the values 1, 2, and 3. You could next insert, say, 5 into the new tree (obtaining a tree containing 1, 2, 3, 4, and 5) or into the old tree (obtaining a tree containing 1, 2, 3, and 5).

The simplest technique for implementing insertion into an immutable tree is called path-copying, because the entire path from the root to the site of the insertion is copied. Nodes not on this path are shared by the two trees. For example, if we insert 6 into the tree on the left in the picture below, we get the tree on the right.

Notice that the nodes containing 3 and 5 were copied, but that the nodes containing 1, 2, and 4 are members of both trees. Even though the two trees contain a total of 11 elements, those elements are represented using only 8 nodes.

If we start with an empty tree and perform N insertions, then we end up with a total of N non-empty trees. However, some of those trees may now be garbage, meaning that they are no longer needed and can be deallocated. When we deallocate a tree, we deallocate all of its nodes, except for those nodes that also belong to trees that are not garbage. You must determine how many nodes remain after deallocating all nodes that can be deallocated.

A series of insertions is represented by a int[] values and a int[] trees. Let N be the number of insertions that are performed. The insertions are numbered from 0 to N-1. Insertion number I is specified by element I of values and element I of trees. Element I of values is the value that is inserted during the insertion, and element I of trees is the number of the tree that the value is inserted into, where tree number J is the result of insertion number J. If element I of trees is -1, then the value is inserted into the empty tree.

For example, the inputs

     values = {  8,  6,  4,  7,  9,  1 }
     trees  = { -1,  0,  1,  0, -1,  2 }

correspond to the following series of insertions:

     tree0 = insert(8,empty)
     tree1 = insert(6,tree0)
     tree2 = insert(4,tree1)
     tree3 = insert(7,tree0)
     tree4 = insert(9,empty)
     tree5 = insert(1,tree2)

The int[] garbage contains the numbers of the trees that are to be deallocated. In the example above, if garbage = {3,1,5}, then tree3, tree1, and tree5 are deallocated, but tree0, tree2, and tree4 are not. You should return the total number of nodes that remain after the garbage trees have been deallocated.