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.