In this programming question, you are asked to implement a special type of binary search trees called DupBinarySearchTree that can accept duplicate...

In this programming question, you are asked to implement a special type of binary search trees called DupBinarySearchTree that can accept duplicate values. In principal, DupBinarySearchTree is mostly identical to a binary search tree, except that it has one extra pointer mLink (called middle link pointer) to keep track of the duplicate values. For example, the following DupBinarySearchTree corresponds to the input sequence

3 2 1 2 3 1 4 1 1 5 (with the first 3 as the root).

Here, each node in the DupBinarySearchTree has its info, and three pointers: left (lLink), middle (mLink) and right (rLink) links to point to nodes whose info are less than, exactly equal and greater than the current node. For instance, the root with info 3 has three links corresponding to nodes with info 2, 3 and 4 as indicated in the picture while the node with info 1 and its three duplicates has only one middle link. The definition of tree height on a BST also applies on DupBinarySearchTree.

Sample output 01

Enter integers (999 to stop): 3 2 1 2 3 1 4 1 1 5 999 Printing sorted tree WITHOUT duplicates:

12345

Printing sorted tree WITH duplicates: 1111223345