I could really use some help with this data structures problem

I'm using c++ and the header and template files I'm using are below.

// FILE: bintree.template // IMPLEMENTS: The binary_tree node class (see bintree.h for documentation). #include // Provides assert #include // Provides NULL, std::size_t #include // Provides std::setw #include // Provides std::cout

namespace main_savitch_10 { template void inorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { inorder(f, node_ptr->left( )); f( node_ptr->data( ) ); inorder(f, node_ptr->right( )); } }

template void postorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { postorder(f, node_ptr->left( )); postorder(f, node_ptr->right( )); f(node_ptr->data( )); } }

template void preorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { f( node_ptr->data( ) ); preorder(f, node_ptr->left( )); preorder(f, node_ptr->right( )); } }

template void print(binary_tree_node* node_ptr, SizeType depth) // Library facilities used: iomanip, iostream, stdlib { if (node_ptr != NULL) { print(node_ptr->right( ), depth+1); std::cout data( ) left( ), depth+1); } } template void tree_clear(binary_tree_node*& root_ptr) // Library facilities used: cstdlib { binary_tree_node* child; if (root_ptr != NULL) { child = root_ptr->left( ); tree_clear( child ); child = root_ptr->right( ); tree_clear( child ); delete root_ptr; root_ptr = NULL; } }

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr) // Library facilities used: cstdlib { binary_tree_node *l_ptr; binary_tree_node *r_ptr;

if (root_ptr == NULL) return NULL; else { l_ptr = tree_copy( root_ptr->left( ) ); r_ptr = tree_copy( root_ptr->right( ) ); return new binary_tree_node( root_ptr->data( ), l_ptr, r_ptr); } }

template size_t tree_size(const binary_tree_node* node_ptr) // Library facilities used: cstdlib { if (node_ptr == NULL) return 0; else return 1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( )); } }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// FILE: bintree.h (part of the namespace main_savitch_10) // PROVIDES: A template class for a node in a binary tree and functions for // manipulating binary trees. The template parameter is the type of data in // each node. // // TYPEDEF for the binary_tree_node template class: // Each node of the tree contains a piece of data and pointers to its // children. The type of the data (binary_tree_node::value_type) is // the Item type from the template parameter. The type may be any of the C++ // built-in types (int, char, etc.), or a class with a default constructor, // and an assignment operator. // // CONSTRUCTOR for the binary_tree_node class: // binary_tree_node( // const item& init_data = Item( ), // binary_tree_node* init_left = NULL, // binary_tree_node* init_right = NULL // ) // Postcondition: The new node has its data equal to init_data, // and it's child pointers equal to init_left and init_right. // // MEMBER FUNCTIONS for the binary_tree_node class: // const item& data( ) const // void inorder(Process f, BTNode* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: If node_ptr is non-NULL, then the function f has been // applied to the contents of *node_ptr and all of its descendants, using // an in-order traversal. // Note: BTNode may be a binary_tree_node or a const binary tree node. // Process is the type of a function f that may be called with a single // Item argument (using the Item type from the node). // // tempate // void postorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a post-order traversal. // // tempate // void preorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a pre-order traversal. // // template // void print(const binary_tree_node* node_ptr, SizeType depth) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). If the pointer is // not NULL, then depth is the depth of the node pointed to by node_ptr. // Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr // and all its descendants have been written to cout with the // void tree_clear(binary_tree_node*& root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: All nodes at the root or below have been returned to the // heap, and root_ptr has been set to NULL. // // template // binary_tree_node* tree_copy(const binary_tree_node* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: A copy of the binary tree has been made, and the return // value is a pointer to the root of this copy. // // template // size_t tree_size(const binary_tree_node* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: The return value is the number of nodes in the tree.

#ifndef BINTREE_H #define BINTREE_H #include // Provides NULL and size_t

namespace main_savitch_10 {

template class binary_tree_node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR binary_tree_node( const Item& init_data = Item( ), binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL ) { data_field = init_data; left_field = init_left; right_field = init_right; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } binary_tree_node* left( ) { return left_field; } binary_tree_node* right( ) { return right_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_left(binary_tree_node* new_left) { left_field = new_left; } void set_right(binary_tree_node* new_right) { right_field = new_right; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const binary_tree_node* left( ) const { return left_field; } const binary_tree_node* right( ) const { return right_field; } bool is_leaf( ) const { return (left_field == NULL) && (right_field == NULL); } private: Item data_field; binary_tree_node *left_field; binary_tree_node *right_field; };

// NON-MEMBER FUNCTIONS for the binary_tree_node: template void inorder(Process f, BTNode* node_ptr);

template void preorder(Process f, BTNode* node_ptr);

template void postorder(Process f, BTNode* node_ptr);

template void print(binary_tree_node* node_ptr, SizeType depth);

template void tree_clear(binary_tree_node*& root_ptr);

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr);

template std::size_t tree_size(const binary_tree_node* node_ptr); }

#include "bintree.template" #endif

The goal of this assignment is to reinforce the tree data structure in C++ Specifically, the assignment is to do the following: Binary search trees have their best performance when they are balanced, which means that at each node, n, the height of the left subtree of n is within one of the height of the right subtree of n. Write a function (and a test program) which takes a sorted list of entries and produces a balanced binary search tree