Description: For this programming assignment, you will implement a class for Binary Tree ADT using a linked structure of nodes, so the tree size grows as elements are inserted into the tree. C++ is prefered.

Coding Portion (50 Points):

A node is supposed to store numbers (integers or floating values).

The insertion operation should be carefully designed so that for every node x, the values in the nodes within the whole left subtree of x is less than or equal to the value in x, and the values in the nodes within the whole right subtree of x is greater than the value in x.

Keep track of the height of the tree while inserting new elements, i.e., you can update the height of the tree whenever you insert a leaf node that in a level greater then the current height of the tree, or you can implement an algorithm to find the height of the tree.

Be sure to test the correctness of your algorithms and implementations.

Your code will be graded based on whether or not it compiles, runs, produces the expected output, produces correct output, whether or not your experimental setup is correct, and your coding style (does the code follow proper indentation/style and comments).

In the end, we have a pseudocode for the insert algorithm. Check if it is correct. If you find an error, explain and correct the error before implementing your algorithm.

//Pseudocode for insert algorithm

Algorithm insert(value, node) Input: value // value to be inserted Output: A pointer to the new added node if node = NULL then node I/root of the (sub)tree // if the tree is empty, this is the root return T.root new Node (value) end if if node.isExternalO then //base case the node new-node new Node (value) if node. value() value then node.leftnew_node else node.rightnewnode end if return new node else recursive step if node.value) s value then return insert(value,node.1eft) else return insert(value,node.right) end if end if