50 Points Consider Following Sequence Numbers 42 8 95 12 71 3 25 69 41 17 32 1 Build Binar Q37101042

1. (50 Points) Consider the following sequence ofnumbers

42 8 95 12 71 3 25 69 41 17 32 1

a) Build a Binary Search Tree (BST). Addnumbers to the tree from left to right order.

b) How many number of comparisons are necessaryto find 41 in the tree?

c) Traverse the tree in-order.

d) Traverse the tree pre-order.

e) Traverse the tree post-order.

2. (50 Points) Consider the following sequence ofnumbers

42 8 95 12 15 3 67 69 41 17 32 1

a) Build an AVL tree. Add numbers to the treefrom left to right order. Show all your steps and rotations thatare necessary for balancing the tree.

b)

OR

 

OR