(Binary Tree Search) Write member function binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The function should take as arguments a pointer to the root node of the binary tree and a search key to be located. If the node containing the search key is found, the function should return a pointer to that node; otherwise, the function should return a null

Question

pointer.

What will be an ideal response?

Answer 1

```
// Definition of class template TreeNode.
#ifndef TREENODE_H
#define TREENODE_H

template< typename T > class Tree; // forward declaration

template< typename NODETYPE >
class TreeNode
{
friend class Tree< NODETYPE >;
public:
TreeNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return data

// return a leftPtr
TreeNode *getLeftPtr() const
{
return leftPtr;
} // end getLeftPtr function

// return a rightPtr
TreeNode *getRightPtr() const
{
return rightPtr;
} // end function getRightPtr

// set value for leftPtr
void setLeftPtr( TreeNode *ptr )
{
leftPtr = ptr;
} // end setLeftPtr function

// set value for rightPtr
void setRightPtr( TreeNode *ptr )
{
rightPtr = ptr;
} // end function setRightPtr
private:
TreeNode *leftPtr; // pointer to left subtree
NODETYPE data;
TreeNode *rightPtr; // pointer to right subtree
}; // end class TreeNode

// constructor
template< typename NODETYPE >
TreeNode< NODETYPE >::TreeNode( const NODETYPE &d )
{
data = d;
leftPtr = rightPtr = 0;
} // end TreeNode constructor

// return a copy of the data value
template< typename NODETYPE >
NODETYPE TreeNode< NODETYPE >::getData() const
{
return data;
} // end function getData

#endif
```
```
// Definition of class template Tree.
#ifndef TREE_H
#define TREE_H

#include
#include
#include "TreeNode.h"
using namespace std;

template< typename NODETYPE >
class Tree
{
public:
Tree();
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;
TreeNode< NODETYPE > *binaryTreeSearch( int ) const;
protected:
TreeNode< NODETYPE > *rootPtr;
private:
// utility functions
void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
TreeNode< NODETYPE >
*binarySearchHelper( TreeNode< NODETYPE > *, int ) const;
}; // end class Tree

// constructor
template< typename NODETYPE >
Tree< NODETYPE >::Tree()
{
rootPtr = 0;
} // end Tree constructor

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

// This function receives a pointer to a pointer so the
// pointer can be modified.
// NOTE: THIS FUNCTION WAS MODIFIED TO ALLOW DUPLICATES.
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr,
const NODETYPE &value )
{
if ( *ptr == 0 ) // tree is empty
*ptr = new TreeNode< NODETYPE >( value );
else // tree is not empty
{
// data to insert is less than data in current node
if ( value <= ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
} // 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 ); // go to left subtree
preOrderHelper( ptr->rightPtr ); // go to 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 ); // go to left subtree
cout << ptr->data << ' '; // process node
inOrderHelper( ptr->rightPtr ); // go to 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
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 )
{
postOrderHelper( ptr->leftPtr ); // go to left subtree
postOrderHelper( ptr->rightPtr ); // go to right subtree
cout << ptr->data << ' '; // process node
} // end if
} // end postOrderHelper

// begin binary search
template< typename NODETYPE >
TreeNode< NODETYPE > *Tree< NODETYPE >::binaryTreeSearch( int val ) const
{
return binarySearchHelper( rootPtr, val );
} // end function binaryTreeSearch

// do a binary search on the Tree
template< typename NODETYPE >
TreeNode< NODETYPE > *Tree< NODETYPE >::binarySearchHelper(
TreeNode< NODETYPE > *ptr, int value ) const
{
// if value is not found
if ( ptr == 0 )
return 0;

cout << "Comparing " << value << " to " << ptr->getData();

if ( value == ptr->getData() ) // match
{
cout << "; search complete\n";
return ptr;
} // end if
else if ( value < ptr->getData() ) // value is less than current data
{
cout << "; smaller, walk left\n";
return binarySearchHelper( ptr->getLeftPtr(), value );
} // end else...if
else // search value is greater than current data
{
cout << "; larger, walk right\n";
return binarySearchHelper( ptr->getRightPtr(), value );
} // end else
} // end function binarySearchHelper

#endif
```
```
#include
#include
#include
using namespace std;

#include "Tree.h"

int main()
{
srand( time( 0 ) ); // randomize the random number generator

Tree< int > intTree;
int intVal;

cout << "The values being placed in the tree are:\n";

// generate a tree with values
for ( int i = 1; i <= 15; i++ )
{
intVal = rand() % 100;
cout << intVal << ' ';
intTree.insertNode( intVal );
} // end for

cout << "\n\nEnter a value to search for: ";
cin >> intVal;

// create a pointer with the user value
TreeNode< int > *ptr = intTree.binaryTreeSearch( intVal );

// a value is found
if ( ptr != 0 )
cout << ptr->getData() << " was found\n";
else // value not found
cout << "Element was not found\n";

cout << endl;
return 0; // indicates successful termination
} // end main
```
The values being placed in the tree are:
3 15 75 24 26 13 12 11 33 17 36 47 28 29 67
Enter a value to search for: 17
Comparing 17 to 3; larger, walk right
Comparing 17 to 15; larger, walk right
Comparing 17 to 75; smaller, walk left
Comparing 17 to 24; smaller, walk left
Comparing 17 to 17; search complete
17 was found