Tree Implementations

Write a 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 log2 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 Traversal, Breadth First Traversal and Best First Traversal (based on priority maximum value in a level) 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