Modify the program of Figs. 20.20–20.22 to allow the binary tree object to contain dupli- cates.

What will be an ideal response?

```
// Tree class template definition.
#ifndef TREE_H
#define TREE_H

#include
using namespace std;

#include "TreeNode.h"

// Tree class-template definition
template< typename NODETYPE > class Tree
{
public:
Tree(); // constructor
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;
private:
TreeNode< NODETYPE > *rootPtr;

// utility functions
void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
}; // end class Tree

// constructor
template< typename NODETYPE >
Tree< NODETYPE >::Tree()
{
rootPtr = 0; // indicate tree is initially empty
} // end Tree constructor

// insert node in Tree
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
} // end function insertNode

// utility function called by insertNode; receives a pointer
// to a pointer so that the function can modify pointer's value
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
// subtree is empty; create new TreeNode containing value
if ( *ptr == 0 )
*ptr = new TreeNode< NODETYPE >( value );
else // subtree is not empty
{
// data to insert is less than or equal to data in current node
if ( value <= ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
{
// data to insert is greater than data in current node
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else // duplicate data value ignored
cout << value << " dup" << endl;
} // end else
} // end else
} // end function insertNodeHelper

// begin preorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
preOrderHelper( rootPtr );
} // end function preOrderTraversal

// utility function to perform preorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
cout << ptr->data << ' '; // process node
preOrderHelper( ptr->leftPtr ); // traverse left subtree
preOrderHelper( ptr->rightPtr ); // traverse right subtree
} // end if
} // end function preOrderHelper

// begin inorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
inOrderHelper( rootPtr );
} // end function inOrderTraversal

// utility function to perform inorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
inOrderHelper( ptr->leftPtr ); // traverse left subtree
cout << ptr->data << ' '; // process node
inOrderHelper( ptr->rightPtr ); // traverse right subtree
} // end if
} // end function inOrderHelper

// begin postorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{
postOrderHelper( rootPtr );
} // end function postOrderTraversal

// utility function to perform postorder traversal of Tree
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
postOrderHelper( ptr->leftPtr ); // traverse left subtree
postOrderHelper( ptr->rightPtr ); // traverse right subtree
cout << ptr->data << ' '; // process node
} // end if
} // end function postOrderHelper

#endif
```
```
// Driver to test class template Tree.
#include
#include
using namespace std;

#include "Tree.h"

int main()
{
Tree< int > intTree;
int intVal;
int i;

cout << "Enter 10 integer values:\n";

// insert input into intTree
for ( i = 0; i < 10; i++ )
{
cin >> intVal;
intTree.insertNode( intVal );
} // end for

cout << "\nPreorder traversal\n";
intTree.preOrderTraversal();

cout << "\nInorder traversal\n";
intTree.inOrderTraversal();

cout << "\nPostorder traversal\n";
intTree.postOrderTraversal();

Tree< double > doubleTree;
double doubleVal;

cout << "\n\n\nEnter 10 double values:\n"
<< fixed << setprecision( 1 );

// takes 10 double values
for ( i = 0; i < 10; i++ )
{
cin >> doubleVal;
doubleTree.insertNode( doubleVal );
} // end for

cout << "\nPreorder traversal\n";
doubleTree.preOrderTraversal();

cout << "\nInorder traversal\n";
doubleTree.inOrderTraversal();

cout << "\nPostorder traversal\n";
doubleTree.postOrderTraversal();
cout << "\n";
return 0; // indicates successful termination
} // end main
```
Enter 10 integer values:
22 8 88 22 73 88 83 68 99 92
Preorder traversal
22 8 22 88 73 68 88 83 99 92
Inorder traversal
8 22 22 68 73 83 88 88 92 99
Postorder traversal
22 8 68 83 88 73 92 99 88 22
Enter 10 double values:
9.9 2.2 8.8 2.2 0.0 6.0 3.4 9.8 5.2 6.3
Preorder traversal
9.9 2.2 2.2 0.0 8.8 6.0 3.4 5.2 6.3 9.8
Inorder traversal
0.0 2.2 2.2 3.4 5.2 6.0 6.3 8.8 9.8 9.9
Postorder traversal
0.0 2.2 5.2 3.4 6.3 6.0 9.8 8.8 2.2 9.9