Q:

What's the running time of computing the size of subtree of every node in a binary tree

When I was doing a binary tree exercise, I had one question that confused me:
Given a binary tree (via a pointer to its root) with n nodes. Let size(n) denote the number of nodes in the subtree rooted at the node n. What is the necessary and sufficient time to compute size(n) for every node n of the tree?
Can anyone give me some hints on the above question? Thanks in advance!

A:

There are a couple errors in @user1952500 algorithm:

return 0 inside a void function
adds to node->num without giving an initial value
Doesn't traverse child nodes to calculate subtree size

So a fixed version would be:
struct tree
{
    int num;
    struct tree *l;
    struct tree *r;
};

void sizeofnode(tree *node)
{
    if (node) { 
        node->num = 1; // Our size

        if (node->l) {
            sizeofnode(node->l);       // Calculates size of left subtree
            node->num += node->l->num; // Adds size of left subtree
        }

        if (node->r) {
            sizeofnode(node->r);       // Calculates size of right subtree
            node->num += node->r->num; // Adds size of right subtree
        }
    }
}

A:

If you can have O(n) space then you can have a O(n) solution:
Here 'num' is the reason of the O(n) space.
struct tree
{
    int num;
    struct tree *l;
    struct tree *r;
};

void sizeofnode(tree *node)
{
    if (!node) {
        return;
    }
    node->num = 0;

    if (node->l) {
        node->num += node->l->num; // size of left subtree
    }

    if (node->r) {
        node->num += node->r->num; // size of right subtree
    }

    node->num ++; // this is to add the size of the root of the subtree

    return;
}

