struct TreeNode {
    int key;
    TreeNode *left, *right;
};

// size() solution

int
subtree_size(TreeNode* node)
{
    if (node == NULL) {
        return 0;
    } else {
        return 1 + subtree_size(node->left)
                 + subtree_size(node->right);
    }
}

int
BinaryTree::size()
{
    return subtree_size(root);
}

// sum_elements solution

int
subtree_sum(TreeNode* node)
{
    if (node == NULL) {
        return 0;
    } else {
        return node->key + sum_helper(node->left)
                         + sum_helper(node->right);
    }
}

int
BinaryTree::sum_elements()
{
    return subtree_sum(root);
}

// count_leaves solution

int
subtree_leafcount(TreeNode* node)
{
    if (node == NULL) {
        // Null tree has no leaves
        return 0;
    } else {
        if (node->left == NULL && node->right == NULL) {
            // The single leaf node has one leaf node.
            return 1;
        } else {
            // Otherwise, we count the leaves of subtrees.
            return subtree_leafcount(node->left)
                   + subtree_leafcount(node->right);
        }
    }
}

int
BinaryTree::count_leaves()
{
    return subtree_leafcount(root);
}

// find_min solutions, recursive and iterative

int
recursive_min(TreeNode* node)
{
    if (node->left == NULL) {
        // Leftmost child: must be min
        return node->key;
    } else {
        // Otherwise, the leftmost child of the left subtree
        // must be the min, so recurse.
        return recursive_min(node->left);
    }
}

// May be used as a drop-in replacement for recursive_min.
int
iterative_min(TreeNode* node)
{
    // Just a reminder.  Redundant, if called from
    // BinaryTree::find_min.
    assert(node != NULL);

    // Simply keep going left until you can't go left any further.
    TreeNode* current = node;
    while (current->left != NULL)
        current = current->left;

    return current->key;
}

int
BinaryTree::find_min()
{
    // The min of an empty tree is meaningless.
    assert(root != NULL);

    return recursive_min(root);
}

// count_odd_depth() solution

int
count_odd_subtree(TreeNode* node, bool is_odd_depth)
{
    if (node == NULL) {
        return 0;
    } else {
        int count_this;
        
        // We only count this node if we are currently at an odd
        // depth.
        if (is_odd_depth) {
            count_this = 1;
        } else {
            count_this = 0;
        }

        // We flip the flag each time.
        return count_this
               + count_odd_subtree(node->left, !is_odd_depth)
               + count_odd_subtree(node->right, !is_odd_depth);
    }
}

int
BinaryTree::count_odd_depth()
{
    // The root is at odd depth (that is, 1), so initially we pass
    // true to the is_odd_depth parameter.
    return count_odd_subtree(root, true);
}