void
inorder_print(TreeNode *node)
{
    if (node == NULL) {
        return;
    } else {
        inorder_print(node->left);  // Visit left
        cout << node->key << endl;  // Visit current
        inorder_print(node->right); // Visit right
    }
}

void
preorder_print(TreeNode *node)
{
    if (node == NULL) {
        return;
    } else {
        cout << node->key << endl;  // Visit current
        preorder_print(node->left);  // Visit left
        preorder_print(node->right); // Visit right
    }
}

void
postorder_print(TreeNode *node)
{
    if (node == NULL) {
        return;
    } else {
        postorder_print(node->left);  // Visit left
        postorder_print(node->right); // Visit right
        cout << node->key << endl;  // Visit current
    }
}

//////////////////////////////////////////////////////////////////////
// EXERCISES

// Note that the following functions define each node to be both an
// ancestor and a descendant of itself.  However, it is actually very
// straightforward to adapt the results to a definition where every
// node is not an ancestor or descendant of itself.

// Recursive ancestor summing
void
accum_ancestors(TreeNode* node, int ancestor_sums)
{
    if (node == NULL) {
        return;
    } else {
        // Use a preorder traversal...

        node->key += ancestor_sums;
        accum_sums(node->left, node->key);
        accum_sums(node->right, node->key);
    }
}

// Wrapper function for the entire process
void
accumulate_ancestor_sums(TreeNode* root)
{
    accum_sums(root, 0);
}

// Recursive descendant summing
void
accum_descendants(TreeNode* node, int &descendant_sums)
{
    if (node == NULL) {
        descendant_sums = 0;
    } else {
        // Uses a postorder traversal
        int left_sum, right;

        accum_descendants(node->left, left_sum);
        accum_descendants(node->right, right_sum);
        node->key += left_sum + right_sum;

        descendant_sums = node->key;
    }
}

// Wrapper function
void
accumulate_descendant_sums(TreeNode* root)
{
    int dummy;
    accum_descendants(root, dummy);

    // Notice that at this point, dummy contains the sum of all
    // the keys in the tree.
}