Problem set week 3

The idea with this problem set is that you should practice on the following things:

• Binary trees.

• Amortised time complexity.

Exercises:

1. Implement an operation which reverses a binary search tree. Explain why it is correct. Analyse its time complexity.

   Modify the binary tree data structure so that reversal can be implemented in constant time. The asymptotic worst-case time complexities of other operations should not change.

2. Consider the following procedure:

   multi-pop(n,s)
      Pops the first n elements from the stack s (n ∈ ℕ).
      Precondition: n ≤ the size of s.
   
      if n > size of s then
        raise error
   
      while n > 0 do
        pop s
        n ← n - 1
   

   What is the worst-case time complexity of multi-pop? What is the best possible amortised time complexity of multi-pop?

   When analysing the time complexity, assume that the stack is implemented as a singly linked list.

Solutions.