The raw topic for the final exam is to build a generic binary search tree that can work with multiple types of data.

This binary search tree will $(1)$ allow for duplicate values in the tree and $(2)$ will NOT use any recursive methods in its implementation. Note that the duplicates do not affect the tree's height.

Sample output:

Enter data types: $1-$Integer, $2-$Double, $3-$Character, $4-$String: $1$

Enter values to the BST: $12-13517161812313-1555$

The tree height: $3$ ;

Enter the key to search: $5$

$5$ is FOUND with $3$ duplicates

$//$ Example $1$: Key is found with no duplicates

Enter a key to delete: $17$

$17$ is deleted from the tree

$//$Example $2$: Key is found with multiple duplicates

Enter a key to delete: $5$

$5$ is deleted with $2$ duplicates left

$//$ Example $3$: Key is not found

Enter a value to delete: $11$

$11$ is NOT FOUND in the tree and is NOT deleted.

Pre$-$Order traversal: $q,$

In$-$Order traversal: $q,$

Post$-$Order traversal: $q,$