#include <iostream>

//--------------------------------------------------------------------------
// Data Definition
// ===============
//  A BinaryTree is either
//      - emptry tree
//   or - a structure consisting of
//          - first as data
//          - rest as a BinaryTree
//--------------------------------------------------------------------------
struct BinaryTree
{
    char        data;
    BinaryTree  *left;
    BinaryTree  *right;
};

//----------------
// Data Examples
//----------------
BinaryTree *empty = 0;
BinaryTree tree1 = { 'a', empty, empty };
BinaryTree tree2 = { 'b', empty, empty };
BinaryTree tree3 = { 'c', &tree1, &tree2 };
BinaryTree tree4 = { 'd', empty, empty };
BinaryTree tree5 = { 'e', &tree3, &tree4 };

//--------------------------------------------------------------------------
// @param T a binary tree
// @return number of nodes in a binary tree
// @description Determine number of nodes in a binary tree
// @contract nNode : BinaryTree -> int
// @example nNode(empty) == 0
// @example nNode(tree1) == 1
// @example nNode(tree2) == 1
// @example nNode(tree3) == 3
// @example nNode(tree4) == 1
// @example nNode(tree5) == 5
//--------------------------------------------------------------------------
int nNode(BinaryTree * T)
{
    if (T == 0)
    {
        return 0;
    }
    else
    {
        return 1 + nNode(T->left) + nNode(T->right);
    }
}

//--------------------------------------------------------------------------
// @param T a binary tree
// @return nothing
// @description Display the tree in an inorder fashion
// @contract showInorder : BinaryTree -> show on screen
// @example showInorder(empty) => ""
// @example showInorder(tree1) => "a"
// @example showInorder(tree2) => "b"
// @example showInorder(tree3) => "cab"
// @example showInorder(tree4) => "d"
// @example showInorder(tree5) => "ecabd
//--------------------------------------------------------------------------
void showInorder(BinaryTree * T)
{
    if (T == 0)
    {
        std::cout << "";
    }
    else
    {
        std::cout << T->data;
        showInorder(T->left);
        showInorder(T->right);
    }
}

//--------------------------------------------------------------------------
// main
//--------------------------------------------------------------------------
int main()
{
    std::cout << "nNode(empty) == " << nNode(empty) << "\n";
    std::cout << "nNode(tree1) == " << nNode(&tree1) << "\n";
    std::cout << "nNode(tree2) == " << nNode(&tree2) << "\n";
    std::cout << "nNode(tree3) == " << nNode(&tree3) << "\n";
    std::cout << "nNode(tree4) == " << nNode(&tree4) << "\n";
    std::cout << "nNode(tree5) == " << nNode(&tree5) << "\n";
    
    showInorder(empty);
    std::cout << "\n";

    showInorder(&tree1);
    std::cout << "\n";

    showInorder(&tree2);
    std::cout << "\n";

    showInorder(&tree3);
    std::cout << "\n";

    showInorder(&tree4);
    std::cout << "\n";

    showInorder(&tree5);
    std::cout << "\n";

    return 0;
}