#include <iostream>

//--------------------------------------------------------------------------
// Data Definition
// A binary tree is either
//  - an empty tree
// or a structure consisting of
//  - data as number
//  - left a binary tree
//  - right as as binary tree
//--------------------------------------------------------------------------
struct BTree
{
    int     data;
    BTree   *left;
    BTree   *right;
};

//--------------------------------------------------------------------------
// Data Example
//--------------------------------------------------------------------------
BTree *empty = 0;
BTree tree1 = { 1, empty, empty };
BTree tree2 = { 2, empty, empty };
BTree tree3 = { 3, &tree1, &tree2 };
BTree tree4 = { 4, empty, empty };
BTree tree5 = { 5, empty, empty };
BTree tree6 = { 6, &tree4, &tree5 };
BTree tree7 = { 7, &tree3, &tree6 };
BTree tree8 = { 8, empty, empty };
BTree tree9 = { 9, &tree8, &tree7 };

//--------------------------------------------------------------------------
// Prototypes
//--------------------------------------------------------------------------
int height(BTree * T);
bool isBalanced(BTree * T);

//--------------------------------------------------------------------------
// main
//--------------------------------------------------------------------------
int main()
{
    std::cout << "height(empty) == " << height(empty) << "\n";
    std::cout << "height(&tree1) == " << height(&tree1) << "\n";
    std::cout << "height(&tree2) == " << height(&tree2) << "\n";
    std::cout << "height(&tree3) == " << height(&tree3) << "\n";
    std::cout << "height(&tree4) == " << height(&tree4) << "\n";
    std::cout << "height(&tree5) == " << height(&tree5) << "\n";
    std::cout << "height(&tree6) == " << height(&tree6) << "\n";
    std::cout << "height(&tree7) == " << height(&tree7) << "\n";
    std::cout << "height(&tree8) == " << height(&tree8) << "\n";
    std::cout << "height(&tree9) == " << height(&tree9) << "\n";

    std::cout << "isBalanced(empty) == " << std::boolalpha << isBalanced(empty) << "\n";
    std::cout << "isBalanced(&tree1) == " << std::boolalpha << isBalanced(&tree1) << "\n";
    std::cout << "isBalanced(&tree2) == " << std::boolalpha << isBalanced(&tree2) << "\n";
    std::cout << "isBalanced(&tree3) == " << std::boolalpha << isBalanced(&tree3) << "\n";
    std::cout << "isBalanced(&tree4) == " << std::boolalpha << isBalanced(&tree4) << "\n";
    std::cout << "isBalanced(&tree5) == " << std::boolalpha << isBalanced(&tree5) << "\n";
    std::cout << "isBalanced(&tree6) == " << std::boolalpha << isBalanced(&tree6) << "\n";
    std::cout << "isBalanced(&tree7) == " << std::boolalpha << isBalanced(&tree7) << "\n";
    std::cout << "isBalanced(&tree8) == " << std::boolalpha << isBalanced(&tree8) << "\n";
    std::cout << "isBalanced(&tree9) == " << std::boolalpha << isBalanced(&tree9) << "\n";

    return 0;
}

//----------------------------------------------------------------------------
// @description determine the larger of two numbers
// @param x the first number
// @param y the second number
// @return the larger of the two numbers
// @contract max2 : int int -> int
// @example max2( 2, 3 ) == 3
// @example max2( 5, 3 ) == 5
// @example max2( 2, -3 ) == 2
//----------------------------------------------------------------------------
int max2(int x, int y)
{
    if (x > y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

//----------------------------------------------------------------------------
// @description determine the height of a binary tree
// @param T a binary tree
// @return the height of a binary tree
// @contract height : Box -> int
// @example height( empty ) == 0
// @example height( tree1 ) == 1
// @example height( tree2 ) == 1
// @example height( tree3 ) == 2
// @example height( tree4 ) == 1
// @example height( tree5 ) == 1
// @example height( tree6 ) == 2
// @example height( tree7 ) == 3
// @example height( tree8 ) == 1
// @example height( tree9 ) == 4
//----------------------------------------------------------------------------
int height(BTree * T)
{
    if (T == 0)
    {
        return 0;
    }
    else
    {
        return 1 + max2( height(T->left), height(T->right) );
    }
}

//----------------------------------------------------------------------------
// @description determine whether a binary tree is balanced
// @param T a binary tree
// @return true if every node in T has the difference between the height of
//         the left subtree and the height of the right subtree is not more
//         than 1
// @contract isBalanced : Box -> bool
// @example isBalanced( empty ) == true
// @example isBalanced( tree1 ) == true
// @example isBalanced( tree2 ) == true
// @example isBalanced( tree3 ) == true
// @example isBalanced( tree4 ) == true
// @example isBalanced( tree5 ) == true
// @example isBalanced( tree6 ) == true
// @example isBalanced( tree7 ) == true
// @example isBalanced( tree8 ) == true
// @example isBalanced( tree9 ) == false
//----------------------------------------------------------------------------
bool isBalanced(BTree * T)
{
    if (T == 0)
    {
        return true;
    }
    else
    {
        return (abs(height(T->left) - height(T->right)) <= 1) &&
                isBalanced(T->left) &&
                isBalanced(T->right);
    }
}