Write a function depth that receives a binary tree and determines how many levels it has.

Question

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;
int getDepth() const;
protected:
TreeNode *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;
void determineDepth( TreeNode< NODETYPE > *, int *, 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

// get the depth of the tree
template< typename NODETYPE >
int Tree< NODETYPE >::getDepth() const
{
int totalDepth = 0;
int currentDepth = 0;

determineDepth( rootPtr, &totalDepth, ¤tDepth );
return totalDepth;
} // end function getDepth

// calculate the depth of the tree
template< typename NODETYPE >
void Tree< NODETYPE >::determineDepth( TreeNode< NODETYPE > *ptr,
int *totPtr, int *currPtr ) const
{
if ( ptr != 0 ) // until ptr points to 0
{
( *currPtr )++;

if ( *currPtr > *totPtr )
*totPtr = *currPtr;

determineDepth( ptr->getLeftPtr(), totPtr, currPtr );
determineDepth( ptr->getRightPtr(), totPtr, currPtr );
( *currPtr )--;
} // end if
} // end function determineDepth

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

#include "Tree.h"

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

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

// inserting value into tree
for ( int i = 0; i < 10; i++ )
{
cin >> intVal;
intTree.insertNode( intVal );
} // end loop

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

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

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

cout << "\n\nThere are " << intTree.getDepth()
<< " levels in this binary tree\n";
return 0; // indicates successful termination
} // end main
```
Enter 10 integer values:
1 2 3 88 4 6 0 22 21 10
Preorder traversal
1 0 2 3 88 4 6 22 21 10
Inorder traversal
0 1 2 3 4 6 10 21 22 88
Postorder traversal
0 10 21 22 6 4 88 3 2 1
There are 9 levels in this binary tree