A tree is a structure which grows from a single root node. By convention, the root node is usually placed at the top. Then, new nodes, referred as children nodes, can be attached to an existing node, referred as parent node, by edges. The root node has no parent and all other nodes have exactly one parent. A node may have any number of children nodes, including no child at all. No looping chain of nodes is permitted in this structure. For example, there are exactly $5$ different types of trees with $4$ nodes. They are shown below. The goal is to find the number of different types of tree with $n$ nodes where $n$ is a positive integer greater than $1$.
The answer is $\boxed{\frac{1}{n}\binom{2(n-1)}{n-1}}$. Or equivalently, there are $\frac{1}{n+1}\binom{2n}{n}$ different types for a tree of $(n+1)$ nodes.
A bijection can be established between this problem and # 4356 using a deep first traversal. The deep first traversal is a recursive visiting algorithm that defines which node to visit next after the current node:
- If the current node dose not have a child node or all its children have been visited, then move back to its parent node
- Otherwise, visit the first child node which has not been visited
The visiting sequence starts and terminates at the root node. For example, in the following tree, the visiting sequence will be $0-1-2-3-2-1-4-1-0$.
Now, let's map such a traversal to a properly matched parentheses sequence in # 4356. A left parenthesis is written when a node, other than the root node, appears the first time in the visiting sequence and a right parenthesis is written when this node appear the last time in the sequence. When a node appears only once in the traversal (i.e. this node has no child), both a left parenthesis and a right one are written. For example, the traversal shown in the diagram above corresponds to the following parentheses sequence: $$((())())$$
Therefore, a tree with $(n+1)$ nodes corresponds to a well matched sequence of $n$ parentheses because the root node does not match any parenthesis. Then the result follows.