#include <iostream>

struct treeNode
{
    char data;
    treeNode* left;
    treeNode* right;
};

int level(treeNode* node)
{
    if (!node)
        return 0;
    return std::max(level(node->left),level(node->right)) + 1;
}

treeNode* insertNode(char data, treeNode* root)
{
    if (!root)
    {
        root = new treeNode;
        root->data = data;
        root->left = root->right = 0;
        return root;
    }
    if (root->data < data)
        root->right = insertNode(data,root->right);
    else
        root->left = insertNode(data,root->left);
}

void printTree(treeNode* root)
{
    if (root)
    {
        printTree(root->left);
        std::cout << root->data << ' ';
        printTree(root->right);
    }
}

bool isLeaf(treeNode* node)
{
    if (node)
        return !node->left && !node->right;
    return false;
}

void removeL(treeNode* node)
{
    if (!node)
        return;

    if (isLeaf(node->left))
    {
        treeNode* del = node->left;
        node->left = 0;
        delete del;
    }

    if (isLeaf(node->right))
    {
        treeNode* del = node->right;
        node->right = 0;
        delete del;
    }

    if (!isLeaf(node->left) && !isLeaf(node->right))
    {
        removeL(node->left);
        removeL(node->right);
    }
}

void prune(treeNode* node)
{
    if (node)
    {
        int leftLevel = level(node->left);
        int rightLevel = level(node->right);
        while (leftLevel != rightLevel)
        {
            if (leftLevel > rightLevel)
            {
                removeL(node->left);
                --leftLevel;
            }
            else if (leftLevel < rightLevel)
            {
                removeL(node->right);
                --rightLevel;
            }
        }
    }
}

void deleteTree(treeNode* root)
{
    if (root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}

int main()
{
    return 0;
}