A-602133 and A-213 both give 

D1= 2 
D2= 1 
D3= 3 
D4= 3

S1=15
S2=5 =D2+D3+1
S3=5 =D1+3
S4=19
S5=11 =D3+D4+5
S6=2 =D2+1
S7=8
S8=6 =D1+D4+1
S9=8 =D3+5
S10=10
S11=6 =D1+D2+3
S12=5 =D4+2
S13=2
S14=11 =D1+D3+6
S15=5 =D2+D4+1
S16=14

1. S= 15, 5, 5, 19, 11, 2, 8, 6, 8, 10, 6, 5, 2, 11, 5, 14

2. Preorder: 15, 5, 19, 6, 11, 5, 2, 8, 8, 10, 6

3. Inorder: 19, 6, 5, 11, 15, 8, 2, 5, 10, 6, 8

4. Postorder: 6, 19, 11, 5, 8, 2, 6, 10, 8, 5, 15

5. 15 5 19 / 6 // 11 // 5 2 8 // / 8 10 / 6 // / 

6. 15 5 5 2 2 // 5 5 // / / 11 8 6 6 // 8 // 10 / 11 // 14 // 19 //

7. cmp 15, left, cmp 5, right, cmp 11, right, cmp 14, left: null -> 13 not in tree.

8. 15 5 5 2 2 // 5 5 // / / 11 8 6 6 // 8 // 10 / 11 // / 19 //

9.  15 5 5 2 2 // 5 5 // / / 11 8 6 6 // / 10 / 11 // / 19 //

10. 2 5 6 15 19 // / 14 // 5 11 // 11 // 2 5 8 // 8 // 5 10 // 6 //

11. structure: min-heap->complete binary tree vs bst->arbitrary ordered binary tree.
order: min-heap-> each parent smaller or equal to each child(ren). Bst -> left descendants smaller or equal to parent. Parent strictly smaller to right descendants.

12. Root has min value, just read the root.

13. Add as last position (constant) then repeatedly move new element upward if strictly smaller than parent. At most ceil(log n) movements given the tree is always complete.

14. (corrected)
2 5 6 15 // 14 // 5 11 // 11 // 5 6 8 // 8 // 5 10 // 19 //

5 5 6 15 // 14 // 5 11 // 11 // 5 6 8 // 8 // 10 19 // /

15. 0 5 5 2 8 2 5 11 5 15 19 6 6 8 11 14 10

16. a possible dfs traversal gives: 
0 5 6 8 11 5 11 6 19 2 2 5 5 14 8 10 15
(there was a typo in the previously published solution: 0 5 6 8 11 2 2 5 5 5 6 11 19 8 10 14 15)
Importantely, use a FIFO queue. Break ties when enqueueing neighbors of a node based on their values.

17. FH FD DC FE FG HJ DA EI DB 

18. It does not contradict as O(n) is included in O(n^2)

19. It does not contradict as O(n) is included in O(n^2)

20. It does not contradict as T(n) might still be in Theta(n^2)

21. It does contradict: if all executions, even the worst ones, are in O(n) then there is no constants c, n0  for which n^2 <= c.T(n) for all n >= n0.

22. No it does not. It would if T(n) was a worst-case, but this might not be the case.

23. Yes it does. If all exectutions are in O(n), then so is it for the worst case. But then there are no c, n0 for which n^2 <= c. T(n) for all n >= n0.

Pb2:

1. According to the description, merge takes constant time if n=2 or less. Otherwise, it calls itself twice on problems of size n/2 then it involves at most n/2-1 comaprisons and swaps.
let k be a constant larger than the times required for comparing and swaping two values.
From the pseudo code, we see: _merge(n) <= k if n <= 2. If n>2: _merge(n) <= 2.merge(n/2) + k.n
One can show by induction (remember array sizes are assumed to be powers of 2) that:
_merge(n) <= 2 . k . n . log(n) where k is larger than the constants of comparing and swaping two values.
For this, show this holds for some n0 (e.g. 2). Assume it for n. Show it for 2.n.

2. _mystery(n) = 2._mystery(n/2)+_merge(n) <= 2._mystery(n/2)+c.n.log(n)

Using similar reasoning and the inequality from 1, one can show by induction that _mystery(n) <= 2.k.n.(log n)^2

For this, show this holds for some n0 (e.g. 2). Assume it for n. Show it for 2.n (remember array sizes are assumed to be powers of 2).