The assignment asks you to write a function that takes a sorted linked list of entries and produces a balanced binary search tree. The function should first build the left subtree of the root, then the right subtree of the root, and finally put the pieces together using the join function.
Contribute Materials
Your contribution can guide someone’s learning journey. Share your
documents today.
Binary search trees have their best performance when they are balanced, which means That at each node, n, the size of the left subtree of n is within one of the size of the left subtree of n is within one of the size of the right subtree of n. Write a function that takes a sorted linked list of entries and produces a balanced binary search tree. If useful, you may add extra parameters to the procedure, such as the total number of entries in the list. Hint: First build the left subtree of the root, then the right subtree of the root, then put the pieces together with the join function from. (please provide test method to it. Just a main method is ok). Template<class Item> void join(bag<Itam>& top, bag<Itam>& left, bag<Item>& right); The precondition of the function requires that top has just one item, that everything in left is less than or equal to the item in top, and that everything in right is greater than the item in top. The postcondition requires that top now contains everything from left and right, and that left and right are now both empty