We showed that the number of binary trees with \(N\) nodes is the Catalan numbers. It is also the number of valid push/pop sequences for \(N\) elements.
Both were derived very differently: One with generating functions and the other using a counting technique. How is it they are the same?
To answer this, let me modify the definition of a node to be that of an internal node. In this binary tree, leaves are not considered nodes, and every node either has other nodes as children, or has a leaf, or a mixture of the two. The tree is necessarily complete. When we speak of the size of this tree, we count only the (internal) nodes.
As a concrete example, consider the following:
Let’s pretend we don’t know that addition is commutative and associative. We could replace \(+\) with any arbitrary binary operator.
The expression above can be evaluated in many ways:
- \((((a+b)+c)+d)\)
- \(((a+b)+(c+d))\)
- \(((a+(b+c))+d)\)
- \((a+((b+c)+d))\)
- \((a+(b+(c+d)))\)
We can represent each of these as a tree: The operations will be the internal nodes, and \(a,b,c,d\) are the leaf nodes.
These correspond to the following trees:
[1, 0, 1, 0, 1, 0]
(((a+b)+c)+d)
o
/
o
/
o
[1, 0, 1, 1, 0, 0]
(((a+b)+c)+d)
o
/ \
o o
[1, 1, 0, 0, 1, 0]
((a+(b+c))+d)
o
/
o
\
o
[1, 1, 0, 1, 0, 0]
(a+((b+c)+d))
o
\
o
/
o
[1, 1, 1, 0, 0, 0]
(a+(b+(c+d)))
o
\
o
\
o
In the trees above, the nodes represent the \(+\) operation. Each node with less than 2 children has one of the leaf nodes attached (not shown).
Take the last example: The bottom node will have \(c\) as its left child, and \(d\) as its right.
So how can we relate these to push/pop sequences? Consider the sequence [1, 0, 1, 1, 0, 0] where 1 is a push and 0 is a pop. We start with a leaf node. Now for every 1 we see (including the first 1), we push a leaf node onto the stack. Every time we see a 0, we pop the last two nodes (leaf or internal), create an internal node, and make the two nodes we popped into its children, and pop this new node back in.
The equivalence doesn’t seem clear. The best I can do is: We can represent any binary tree as a sequence of 1’s and 0’s (which we didn’t do in our prior derivation of the Catalan numbers using generating functions).
We start with a stack, and insert a leaf. This leaf is always there and is not part of our sequence (yes, that’s ugly). Then we go through the sequence of 1’s and 0’s. For every 1, we push a leaf node. For every 0, we pop two nodes, make a new node as the parent of these two, and push this node into the stack. You will get a binary tree. The constraint of there not being more 0’s than 1’s at any stage corresponds to the fact that we must have leaf nodes to perform the addition on: The first addition needs at least two leaf nodes. One of them is the “free” one, the other corresponds to the first 1 in our sequence. After that, if we were to add another plus node, we need two nodes to make its children (its operands). If you follow this logic through, you can’t be in a state of more 0’s than 1’s at any point.
This is a one way transformation. In the other direction: Given a binary tree, how do we construct its sequence?
This is simpler to explain. Do a DFS, starting with the left node. Any time you hit a leaf node and cannot go further, insert a 1. Any time you are backtracking on a \(+\) node, insert a 0.
This is basically a post-order traversal. Then throw away the first 1 at the end.