CountNodes.cpp

/* C89 */
#include <stddef.h> /* size_t */

struct Node {
    struct Node *left;
    struct Node *right;
    void *data;
};

static size_t count_nodes(struct Node root)
{
    size_t n = 1;

    if (root.left)
        n += count_nodes(*root.left);
    if (root.right)
        n += count_nodes(*root.right);

    return n;
}

// C++1z
#include <cstddef> // size_t
#include <optional> // optional
using std::optional;
using std::size_t;

template<class T>
struct Node {
    optional<Node> left;
    optional<Node> right;
    T value;

    constexpr size_t count_nodes() const
    {
        size_t n = 1;

        if (left)
            n += left->count_nodes();
        if (right)
            n += right->count_nodes();

        return n;
    }
};