Today's post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between forests and matched parentheses is simply to consider each `{` as an XML open-tag and each `}` as an XML end-tag.

One thing to take away from the enumeration of objects controlled by Catalan numbers is that when you see multiplication in a recurrence relation, that typically corresponds to a nested loop. (We saw this ourselves when we studied Stirling numbers of the second kind.)

The correspondence between binary trees and arbitrary forests is done by simply renaming variables: `left­Child` and `right­Child` turn into `first­Child` and `next­Sibling`.

Renaming variables also reveals an interesting equivalence between the two algorithms for reversing a linked list. One technique is to do link rewriting:

```Node *Reverse(Node *head)
{
Node *prev = nullptr;
// The node we are rewriting

// Advance to next node before
// we overwrite the outbound pointer

// Repoint to previous node
current->next = prev;

prev = current;
}
return prev;
}
```

Another technique is to pop nodes off one list while pushing them onto another.

```Node *Reverse(Node *head)
{
Node *result = nullptr;
// Pop