#include <iostream>

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

//--------------
// Data Example
//--------------
//         9
//        / \
//       7   8
//      / \
//     3   6
//    /     \
//   2       5
//  /         \
// 1           4
//-------------------------
BTree * empty = 0;
BTree tree_1 = { 1, empty,   empty };
BTree tree_2 = { 2, &tree_1, empty };
BTree tree_3 = { 3, &tree_2, empty };
BTree tree_4 = { 4, empty,   empty };
BTree tree_5 = { 5, empty,   &tree_4 };
BTree tree_6 = { 6, empty,   &tree_5 };
BTree tree_7 = { 7, &tree_3, &tree_6 };
BTree tree_8 = { 8, empty,   empty };
BTree tree_9 = { 9, &tree_7, &tree_8 };

//-------------------------
//             18
//            /  \
//           /    \
//          /      \
//         /       19
//        13      /  \
//       /  \   17   20
//      /    \
//     /      \
//   11       15    
//  /  \     /  \
// 10  14   12  16
//-------------------------
BTree tree_10 = { 10, empty,    empty };
BTree tree_14 = { 14, empty,    empty };
BTree tree_11 = { 11, &tree_10, &tree_14 };
BTree tree_12 = { 12, empty,    empty };
BTree tree_16 = { 16, empty,    empty };
BTree tree_15 = { 15, &tree_12, &tree_16 };
BTree tree_13 = { 13, &tree_11, &tree_15 };
BTree tree_17 = { 17, empty,    empty };
BTree tree_20 = { 20, empty,    empty };
BTree tree_19 = { 19, &tree_17, &tree_20 };
BTree tree_18 = { 9, &tree_13,   &tree_19 };

//--------------
// Code Pattern
//--------------
//... F(BTree * T)
// {
//    if (T == 0)
//    {
//    }
//    else
//    {
//        ... T->data ...
//        ... F(T->left) ...
//        ... F(T->right) ...
//    }
//------------------------------------------------------------------------------

//******************************************************************************
// Prototypes
//******************************************************************************
int max2(int, int);
int maxValueHelper(BTree *, int);
int maxValue(BTree *);
bool isHeapHelper(BTree *, int);
bool isHeap(BTree *);
int largestGap(BTree *);

//******************************************************************************
// main
//******************************************************************************
int main()
{
    std::cout << "max2(2, 3) = " << max2(2, 3) << "\n";
    std::cout << "max2(6, 3) = " << max2(6, 3) << "\n";
    std::cout << "max2(4, 4) = " << max2(4, 4) << "\n";

    std::cout << "maxValueHelper(empty, 5) = " << maxValueHelper(empty, 5) << "\n";
    std::cout << "maxValueHelper(&tree_1, 3) = " << maxValueHelper(&tree_1, 3) << "\n";
    std::cout << "maxValueHelper(&tree_2, 1) = " << maxValueHelper(&tree_2, 1) << "\n";
    std::cout << "maxValueHelper(&tree_3, 4) = " << maxValueHelper(&tree_3, 4) << "\n";
    std::cout << "maxValueHelper(&tree_4, 1) = " << maxValueHelper(&tree_4, 1) << "\n";
    std::cout << "maxValueHelper(&tree_5, 9) = " << maxValueHelper(&tree_5, 9) << "\n";
    std::cout << "maxValueHelper(&tree_6, 4) = " << maxValueHelper(&tree_6, 4) << "\n";
    std::cout << "maxValueHelper(&tree_7, 4) = " << maxValueHelper(&tree_7, 4) << "\n";

    std::cout << "maxValue(empty) = " << maxValue(empty) << "\n";
    std::cout << "maxValue(&tree_1) = " << maxValue(&tree_1) << "\n";
    std::cout << "maxValue(&tree_2) = " << maxValue(&tree_2) << "\n";
    std::cout << "maxValue(&tree_3) = " << maxValue(&tree_3) << "\n";
    std::cout << "maxValue(&tree_4) = " << maxValue(&tree_4) << "\n";
    std::cout << "maxValue(&tree_5) = " << maxValue(&tree_5) << "\n";
    std::cout << "maxValue(&tree_6) = " << maxValue(&tree_6) << "\n";
    std::cout << "maxValue(&tree_7) = " << maxValue(&tree_7) << "\n";

    std::cout << "isHeapHelper(empty, 9) = " << std::boolalpha << isHeapHelper(empty, 9) << "\n";
    std::cout << "isHeapHelper(&tree_1, 9) = " << std::boolalpha << isHeapHelper(&tree_1, 9) << "\n";
    std::cout << "isHeapHelper(&tree_2, 9) = " << std::boolalpha << isHeapHelper(&tree_2, 9) << "\n";
    std::cout << "isHeapHelper(&tree_3, 9) = " << std::boolalpha << isHeapHelper(&tree_3, 9) << "\n";
    std::cout << "isHeapHelper(&tree_4, 9) = " << std::boolalpha << isHeapHelper(&tree_4, 9) << "\n";
    std::cout << "isHeapHelper(&tree_5, 9) = " << std::boolalpha << isHeapHelper(&tree_5, 9) << "\n";
    std::cout << "isHeapHelper(&tree_6, 9) = " << std::boolalpha << isHeapHelper(&tree_6, 9) << "\n";
    std::cout << "isHeapHelper(&tree_7, 9) = " << std::boolalpha << isHeapHelper(&tree_7, 9) << "\n";
    std::cout << "isHeapHelper(&tree_8, 9) = " << std::boolalpha << isHeapHelper(&tree_8, 9) << "\n";
    std::cout << "isHeapHelper(&tree_9, 9) = " << std::boolalpha << isHeapHelper(&tree_9, 9) << "\n";
    std::cout << "isHeapHelper(&tree_10, 9) = " << std::boolalpha << isHeapHelper(&tree_10, 9) << "\n";
    std::cout << "isHeapHelper(&tree_11, 9) = " << std::boolalpha << isHeapHelper(&tree_11, 9) << "\n";
    std::cout << "isHeapHelper(&tree_12, 9) = " << std::boolalpha << isHeapHelper(&tree_12, 9) << "\n";
    std::cout << "isHeapHelper(&tree_13, 9) = " << std::boolalpha << isHeapHelper(&tree_13, 9) << "\n";
    std::cout << "isHeapHelper(&tree_14, 9) = " << std::boolalpha << isHeapHelper(&tree_14, 9) << "\n";
    std::cout << "isHeapHelper(&tree_15, 9) = " << std::boolalpha << isHeapHelper(&tree_15, 9) << "\n";
    std::cout << "isHeapHelper(&tree_16, 9) = " << std::boolalpha << isHeapHelper(&tree_16, 9) << "\n";
    std::cout << "isHeapHelper(&tree_17, 9) = " << std::boolalpha << isHeapHelper(&tree_17, 9) << "\n";
    std::cout << "isHeapHelper(&tree_18, 9) = " << std::boolalpha << isHeapHelper(&tree_18, 9) << "\n";
    std::cout << "isHeapHelper(&tree_19, 9) = " << std::boolalpha << isHeapHelper(&tree_19, 9) << "\n";
    std::cout << "isHeapHelper(&tree_20, 9) = " << std::boolalpha << isHeapHelper(&tree_20, 9) << "\n";

    std::cout << "isHeap(empty) = " << std::boolalpha << isHeap(empty) << "\n";
    std::cout << "isHeap(&tree_1) = " << std::boolalpha << isHeap(&tree_1) << "\n";
    std::cout << "isHeap(&tree_2) = " << std::boolalpha << isHeap(&tree_2) << "\n";
    std::cout << "isHeap(&tree_3) = " << std::boolalpha << isHeap(&tree_3) << "\n";
    std::cout << "isHeap(&tree_4) = " << std::boolalpha << isHeap(&tree_4) << "\n";
    std::cout << "isHeap(&tree_5) = " << std::boolalpha << isHeap(&tree_5) << "\n";
    std::cout << "isHeap(&tree_6) = " << std::boolalpha << isHeap(&tree_6) << "\n";
    std::cout << "isHeap(&tree_7) = " << std::boolalpha << isHeap(&tree_7) << "\n";
    std::cout << "isHeap(&tree_8) = " << std::boolalpha << isHeap(&tree_8) << "\n";
    std::cout << "isHeap(&tree_9) = " << std::boolalpha << isHeap(&tree_9) << "\n";
    std::cout << "isHeap(&tree_10) = " << std::boolalpha << isHeap(&tree_10) << "\n";
    std::cout << "isHeap(&tree_11) = " << std::boolalpha << isHeap(&tree_11) << "\n";
    std::cout << "isHeap(&tree_12) = " << std::boolalpha << isHeap(&tree_12) << "\n";
    std::cout << "isHeap(&tree_13) = " << std::boolalpha << isHeap(&tree_13) << "\n";
    std::cout << "isHeap(&tree_14) = " << std::boolalpha << isHeap(&tree_14) << "\n";
    std::cout << "isHeap(&tree_15) = " << std::boolalpha << isHeap(&tree_15) << "\n";
    std::cout << "isHeap(&tree_16) = " << std::boolalpha << isHeap(&tree_16) << "\n";
    std::cout << "isHeap(&tree_17) = " << std::boolalpha << isHeap(&tree_17) << "\n";
    std::cout << "isHeap(&tree_18) = " << std::boolalpha << isHeap(&tree_18) << "\n";
    std::cout << "isHeap(&tree_19) = " << std::boolalpha << isHeap(&tree_19) << "\n";
    std::cout << "isHeap(&tree_20) = " << std::boolalpha << isHeap(&tree_20) << "\n";

    std::cout << "largestGap(empty) = " << largestGap(empty) << "\n";
    std::cout << "largestGap(&tree_1) = " << largestGap(&tree_1) << "\n";
    std::cout << "largestGap(&tree_2) = " << largestGap(&tree_2) << "\n";
    std::cout << "largestGap(&tree_3) = " << largestGap(&tree_3) << "\n";
    std::cout << "largestGap(&tree_4) = " << largestGap(&tree_4) << "\n";
    std::cout << "largestGap(&tree_5) = " << largestGap(&tree_5) << "\n";
    std::cout << "largestGap(&tree_6) = " << largestGap(&tree_6) << "\n";
    std::cout << "largestGap(&tree_7) = " << largestGap(&tree_7) << "\n";
    std::cout << "largestGap(&tree_8) = " << largestGap(&tree_8) << "\n";
    std::cout << "largestGap(&tree_9) = " << largestGap(&tree_9) << "\n";

    return 0;
}

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

//------------------------------------------------------------------------------
// @description determine the maximum value in a binary tree
// @param T a binary tree
// @param acc the maximum value so far
// @return 'Error if the T is empty, otherwise the maximum of a binary tree
// @contract maxValueHelper: BT number -> number
// @example maxValueHelper(empty, 5) = 5
// @example maxValueHelper(&tree_1, 3) = 3
// @example maxValueHelper(&tree_2, 1) = 2
// @example maxValueHelper(&tree_3, 4) = 4
// @example maxValueHelper(&tree_4, 1) = 4
// @example maxValueHelper(&tree_5, 9) = 9
// @example maxValueHelper(&tree_6, 4) = 6
// @example maxValueHelper(&tree_7, 4) = 7
//------------------------------------------------------------------------------
int maxValueHelper(BTree * T, int acc)
{
    if (T == 0)
    {
        return acc;
    }
    else
    {
        return max2(maxValueHelper(T->left, max2(T->data, acc)),
                    maxValueHelper(T->right, max2(T->data, acc)));
    }
}

//------------------------------------------------------------------------------
// @description determine the maximum value in a binary tree
// @param T a binary tree
// @return 'Error if the T is empty, otherwise the maximum of a binary tree
// @contract maxValue: BT -> number or 'Error
// @example maxValue(empty) = 'Error
// @example maxValue(&tree_1) = 1
// @example maxValue(&tree_2) = 2
// @example maxValue(&tree_3) = 3
// @example maxValue(&tree_4) = 4
// @example maxValue(&tree_5) = 5
// @example maxValue(&tree_6) = 6
// @example maxValue(&tree_7) = 7
//------------------------------------------------------------------------------
int maxValue(BTree * T)
{
    if (T == 0)
    {
        std::cerr << "Error!";
        return 0;
    }
    else
    {
        return max2( maxValueHelper(T->left, T->data),
                     maxValueHelper(T->right, T->data) );
    }
}

//------------------------------------------------------------------------------
// @description determine whether the value of the current node is less than the
//              value of v
// @param T a binary tree
// @param v a value to be compared to
// @return true if T is empty or T->data < v, false otherwise
// @contract isHeap: BT number -> boolean
// @example isHeapHelper(empty, 9) = true
// @example isHeapHelper(&tree_1, 9) = true
// @example isHeapHelper(&tree_2, 9) = true
// @example isHeapHelper(&tree_3, 9) = true
// @example isHeapHelper(&tree_4, 9) = true
// @example isHeapHelper(&tree_5, 9) = true
// @example isHeapHelper(&tree_6, 9) = true
// @example isHeapHelper(&tree_7, 9) = true
// @example isHeapHelper(&tree_8, 9) = true
// @example isHeapHelper(&tree_9, 9) = false
// @example isHeapHelper(&tree_10, 9) = false
// @example isHeapHelper(&tree_11, 9) = false
// @example isHeapHelper(&tree_12, 9) = false
// @example isHeapHelper(&tree_13, 9) = false
// @example isHeapHelper(&tree_14, 9) = false
// @example isHeapHelper(&tree_15, 9) = false
// @example isHeapHelper(&tree_16, 9) = false
// @example isHeapHelper(&tree_17, 9) = false
// @example isHeapHelper(&tree_18, 9) = false
// @example isHeapHelper(&tree_19, 9) = false
// @example isHeapHelper(&tree_20, 9) = false
//------------------------------------------------------------------------------
bool isHeapHelper(BTree * T, int v)
{
    if (T == 0)
    {
        return true;
    }
    else
    {
        return (T->data < v);
    }
}

//------------------------------------------------------------------------------
// @description determine whether a binary tree is a heap tree
// @note a heap tree is a binary tree such that for every node, the values in the
//       subtrees are less than the value in the current node.
// @param T a binary tree
// @return true if a binary tree is a binary search tree
// @contract isHeap: BT -> boolean
// @example isHeap(empty) = true
// @example isHeap(&tree_1) = true
// @example isHeap(&tree_2) = true
// @example isHeap(&tree_3) = true
// @example isHeap(&tree_4) = true
// @example isHeap(&tree_5) = true
// @example isHeap(&tree_6) = true
// @example isHeap(&tree_7) = true
// @example isHeap(&tree_8) = true
// @example isHeap(&tree_9) = true
// @example isHeap(&tree_10) = true
// @example isHeap(&tree_11) = false
// @example isHeap(&tree_12) = true
// @example isHeap(&tree_13) = false
// @example isHeap(&tree_14) = true
// @example isHeap(&tree_15) = false
// @example isHeap(&tree_16) = true
// @example isHeap(&tree_17) = true
// @example isHeap(&tree_18) = false
// @example isHeap(&tree_19) = false
// @example isHeap(&tree_20) = true
//------------------------------------------------------------------------------
bool isHeap(BTree * T)
{
    if (T == 0)
    {
        return true;
    }
    else
    {
        return isHeapHelper(T->left, T->data) &&
               isHeapHelper(T->right, T->data) &&
               isHeap(T->left) &&
               isHeap(T->right);
    }
}


//------------------------------------------------------------------------------
// @description determine the largest gap between two adjacent nodes in a binary
//              tree
// @param T a binary tree
// @return 0 if T is empty or has only one node, otherwise the largest gap
//         between two adjacent nodes
// @contract largestGap: BT -> number
// @example largestGap(empty) = 0
// @example largestGap(tree_1) = 0
// @example largestGap(tree_2) = 1
// @example largestGap(tree_3) = 1
// @example largestGap(tree_4) = 0
// @example largestGap(tree_5) = 1
// @example largestGap(tree_6) = 1
// @example largestGap(tree_7) = 4
// @example largestGap(tree_8) = 0
// @example largestGap(tree_9) = 4
//------------------------------------------------------------------------------
int largestGap(BTree * T)
{
    if (T == 0)
    {
        return 0;
    }
    else if (T->left == 0 && T->right == 0)
    {
        return 0;
    }
    else if (T->left == 0)      // but T->right != 0
    {
        return max2( abs(T->data - T->right->data),
                     largestGap(T->right) );
    }
    else if (T->right == 0)
    {
        return max2( abs(T->data - T->left->data),
                     largestGap(T->left) );
    }
    else
    {
        return max2( max2( abs(T->data - T->left->data),
                           abs(T->data - T->right->data) ),
                     max2( largestGap(T->left),
                           largestGap(T->right) ) );
    }
}