Question: Consider the tree algorithm in Fig. Given that k collisions occur in a CRP, determine the number of slots required for the CRP. Check your answer with the particular example of Fig.
Hint 1: Note that each collision corresponds to a nonleaf node of the rooted tree. Consider "building" any given tree from the root up, successively replacing leaf nodes by internal nodes with two upward-going edges.
Hint 2: For another approach, consider what happens in the stack for each collision, idle, or success.
