Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 3

Problem:

You are given a binary tree (via a pointer to its root) with n nodes. As in lecture, let $size(x)$ denote the number of nodes in the subtree rooted at the node $x$. How much time is necessary and sufficient to compute $size(x)$ for every node $x$ of the tree?

Solution:

A simple algorithm like this can compute all the size in $O(n)$ time

function compute_size(node)
  if (node == null)
    return 0;
  size = compute_size(node.left) + 1 + compute_size(node.right);
  node.size = size;
  return size;

The lower bound for this case is trivial, the algorithm must report the size of all nodes, the reporting alone will take $\Omega(n)$ time.