#include <iostream>
using namespace std;
typedef int Data;

struct TreeNode
{
    TreeNode(Data d):data(d){left = right = NULL;};
    Data data;
    TreeNode* left;
    TreeNode* right;
};

class Tree
{
public:
    Tree():root(NULL){};
    TreeNode* root;
    void insert(Data data, TreeNode* node = NULL)
    {
        if(root == NULL)
        {
            root = new TreeNode(data);
            return;
        }
        if(node == NULL) node = root;
        if(data == node->data)
        {
            return;
        } else if(data < node->data) {
            if(node->left == NULL)
                node->left = new TreeNode(data);    
            else
                insert(data, node->left);
        } else {
            if(node->right == NULL)
                node->right = new TreeNode(data);
            else
                insert(data, node->right);
        }
    };
    void inorderPrint(TreeNode* TreeNode)
    {
        if(TreeNode == root)
            cout<<"Print:"<<endl;
        if(TreeNode != NULL)
        {
            inorderPrint(TreeNode->left);
            cout<<TreeNode->data<<" ";
            inorderPrint(TreeNode->right);
        }
        if(TreeNode == root)
            cout<<endl<<"End"<<endl;
    };
    void preorderPrint(TreeNode* TreeNode)
    {
        if(TreeNode == root)
            cout<<"Print:"<<endl;
        if(TreeNode != NULL)
        {
            cout<<TreeNode->data<<" ";
            preorderPrint(TreeNode->left);
            preorderPrint(TreeNode->right);
        }
        if(TreeNode == root)
            cout<<endl<<"End"<<endl;
    };
    void postorderPrint(TreeNode* node)
    {
        if(node == root)
            cout<<"Print:"<<endl;
        if(node != NULL)
        {
            postorderPrint(node->left);
            postorderPrint(node->right);
            cout<<node->data<<" ";
        }
        if(node == root)
            cout<<endl<<"End"<<endl;
    };
    bool isBalanced()
    {
        int min=0 ,max=0;
        calDepth(root, 0, &min, &max);
        cout<<"Min: "<<min<<endl<<"Max: "<<max<<endl;
        if(max - min < 2)
            return true;
        else
            return false;
    };
    void calDepth(TreeNode* node, int depth, int* min, int* max)
    {
        if(node == NULL) return;
        depth++;
        if(node->left == NULL && node->right == NULL)
        {
            if(depth < *min || *min <= 0)
                *min = depth;
            if(depth > *max || *max <= 0)
                *max = depth;
        }
        calDepth(node->left, depth, min, max);
        calDepth(node->right, depth, min, max);
    };
};

int main()
{
    Tree tree;
    tree.insert(5);
    tree.insert(1);
    tree.insert(7);
    tree.insert(4);
    tree.insert(3);
    cout<<boolalpha<<tree.isBalanced();
    system("pause");
};