Part #1. Given an array of integers, design an algorithm and implement in C++ to construct a balanced binary search tree (BST). In a balanced BST, the heights of all leaf nodes can differ at most by 1. As an example, given an input array (3, 2, 1, 4, 6, 5), here are examples of balanced BST versus unbalanced BST:
In the above example, the left BST is balanced because the difference of heights for all the leaf nodes is less than 1. The right BST is unbalanced because the difference of height for some leaf nodes ( "3" and 1) is 2, which is larger than 1.
Note that the integers in the given array may not be sorted.
You should utilize the data structure and methods defined in the codes BST.h and BST.cpp, and implement this part in a "driver" program.
Part #2. Conduct an in-order traversal of the BST you constructed in Part #1 and print out the nodes in that order. You may re-use the inOrder traversal method you developed in the programming assignment.
Part #3. Implement a new method in BST.cpp (named as LeafHeights) that calculates and prints out the heights of all the leaf nodes of the BST constructed in Part #1. The driver program should call this method. For the example of balanced BST in Part #1, there are 3 leaf nodes: 1, 4, and 6. It should print
Height of leaf "1": 2
Height of leaf "4": 2
Height of leaf "6": 2
Part #4. Implement a new method in BST.cpp (named as "NewSearch") that, for a given number N (input from user), finds the node in the BST (constructed in Part #1) that has the value equal to or the smallest number greater than N. For the example in Part #1, if N=0, the found number should be 1. If N=7, then there is no such number.