#include <assert.h>    // Provides assert
#include <iomanip.h>   // Provides setw
#include <iostream.h>  // Provides cout
#include <stdlib.h>    // Provides NULL, size_t
template <class Item>
struct BinaryTreeNode
{
        Item data;
        BinaryTreeNode* left;
        BinaryTreeNode* right;
};

template <class Item>
BinaryTreeNode<Item>* create_node(
    const Item& entry,
    BinaryTreeNode<Item>* l_ptr = NULL,
    BinaryTreeNode<Item>* r_ptr = NULL
)
{
    BinaryTreeNode<Item>* result_ptr;

    result_ptr = new BinaryTreeNode<Item>;
    result_ptr->data  = entry;
    result_ptr->left  = l_ptr;
    result_ptr->right = r_ptr;

    return result_ptr;
}

template <class Item>
BinaryTreeNode<Item>* tree_copy(const BinaryTreeNode<Item>* root_ptr)
{
    BinaryTreeNode<Item> *l_ptr;
    BinaryTreeNode<Item> *r_ptr;

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

template <class Item>
void tree_clear(BinaryTreeNode<Item>*& root_ptr)
{
    if (root_ptr != NULL)
    {
        tree_clear(root_ptr->left);
        tree_clear(root_ptr->right);
        delete root_ptr;
        root_ptr = NULL;
    }
}

template <class Item>
bool is_leaf(const BinaryTreeNode<Item>& node)
{
    return (node.left == NULL) && (node.right == NULL);
}

template <class Process, class Item>
void inorder(Process f, BinaryTreeNode<Item>* node_ptr)
{
    if (node_ptr != NULL)
    {
        inorder(f, node_ptr->left);
        f(node_ptr->data);
        inorder(f, node_ptr->right);
    }
}

template <class Process, class Item>
void postorder(Process f, BinaryTreeNode<Item>* node_ptr)
{
    if (node_ptr != NULL)
    {
        postorder(f, node_ptr->left);
        postorder(f, node_ptr->right);
        f(node_ptr->data);
    }
}

template <class Process, class Item>
void preorder(Process f, BinaryTreeNode<Item>* node_ptr)
{
    if (node_ptr != NULL)
    {
        f(node_ptr->data);
        preorder(f, node_ptr->left);
        preorder(f, node_ptr->right);
    }
}

template <class Item, class SizeType>
void print(BinaryTreeNode<Item>* node_ptr, SizeType depth)
{
    if (node_ptr != NULL)
    {
        print(node_ptr->right, depth+1);
        cout << setw(4*depth) << ""; // Indent 4*depth spaces
        cout << node_ptr->data << endl;
        print(node_ptr->left, depth+1);
    }
}

template <class Item>
size_t tree_size(const BinaryTreeNode<Item>* node_ptr)
{
    if (node_ptr == NULL)
        return 0;
    else
        return 1 + tree_size(node_ptr->left) + tree_size(node_ptr->right);
}