data structures needed asap. upvote will given a. Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 45. Which (possibly multiple) of the following sequences could be the sequence of nodes examined in order?

5, 2, 1, 10, 39, 34, 77, 63.

1, 2, 3, 4, 5, 6, 7, 8.

9, 8, 63, 0, 4, 3, 2, 1.

8, 7, 6, 5, 4, 3, 2, 1.

50, 25, 26, 27, 40, 44, 42.

50, 25, 26, 27, 40, 44.

b. Suppose you insert the numbers 1,2,3 into an AVL tree. How many rotations are there?

Suppose you insert the numbers 1,2,3,4,5,6,7 into an AVL tree. How many rotations are there?

Suppose in general you insert the numbers 1,2,3,,2^k-1, for some positive integer k, into an AVL tree. How many rotations are there in terms of k?

You do NOT need to prove your answer.