Write a java program to:

(a) Build a fully left skewed binary search tree (BST) with 26 levels and output the corresponding complete balanced BST. You must demonstrate through your program the insertion of elements starting with an empty BST and then implement the balance operation to convert it into a balanced BST. You can choose numeric (1, 2, 3 26) or alphabetic (A, B, C, Z) data values to build your BST. You need to compute midpoints for each division. You need to perform the divisions until log₂ 26 numbers of iterations. Your implementation should:

Input the data values and build the unbalanced BST

Build the BST for the best height (balanced tree)

Output the balanced BST

Compute the system time for both the tree data structures (balanced and unbalanced)

(b) Implement Depth First (Pre- or post-fix) and Breadth First Traversal for both the unbalanced and balanced search trees. Your implementation should:

Output the traversal order

Compute the system time for all traversals both the balanced and unbalanced trees.