total number of ordered tree with 3 nodes

algorithm data-structures tree binary-tree ordered-tree

17,625

Solution 1

Refer to the following link, it is a really nice paper on counting number of ordered trees.

Solution 2

First off, yes your example is a tree under any reasonable definition, unless you are requiring the tree to be "full" which is mentioned nowhere. I suspect, therefore, that the answers on both of those pages are (not surprisingly) wrong.

Secondly, I don't like the way the question is worded in the second link since it doesn't make clear what is meant by equality. Are we just looking for trees that are topologically the same (same structure, that is, placement of nodes) or are we looking for equality of trees that contain a set of three specific nodes, like in the first link. So, I'll stick to the question in the first link.

I'm using the following definition of an ordered tree. Because it doesn't matter for this question, I'm going to ignore the edge case of an empty tree, although a definition could be written to include the empty tree as a candidate if desired. An ordered tree consists of a root node together with a possibly empty list (an ordered sequence) of children, each of which is also an ordered tree.

This definition clearly includes your example. The root is A, it has a single child, B, which has a single child C, which has no children (an empty list of children).

Let's proceed recursively on the number of nodes N that we are placing into a tree. We'll let T(N) be the number of distinct ordered trees that can be constructed from a fixed set of N (labeled) nodes.

Base Case: N = 1. If we have exactly one node we can construct only one tree where that node is the root. So T(1) = 1.

Second Case: N = 2. There are two choices for the root node. The remaining node is necessarily the first and only child of the root. So T(2) = 2.

Third Case: N = 3. There are now three choices for the root node. Once we've selected a root node, we again have two cases:

Case A: The root node has two children, each of which is an ordered tree with two elements. There are two ways we could order the two remaining nodes. So there are 3*2 = 6 possible ordered trees with three nodes given that the root node has two children.
Case B: The root node has one child, which is necessarily an ordered tree with two elements. There are T(2) = 2 different ways we could construct an ordered tree from the remaining two elements, so there are a total of 3*2 = 6 possible ordered trees with three nodes given that the root node has only one child.

These two subcases cover all the possibilities and they don't overlap (they partition the possible ordered trees with three nodes), so we can just add them: T(3) = 6 + 6 = 12.

If you are interested in the more general question, it is a bit trickier and I do not know the answer, nor do I know if the answer is known. The approach I would take would be something like this:

General Case: N. There is one root. The remaining N - 1 nodes must lie in subtrees of the root. So you would look at the partition number of N - 1 (the number of ways of breaking N - 1 up into groups). Then would would have to look at the number of ways of choosing the items that go into each group. And then you would look at the number of ordered trees that could be made from the number of nodes that are in each group.

Anyway, there are other approaches. But that is perhaps beyond the scope of this question.

NOTE: One question that may arise is whether or not I forgot to count something like

    A                      A
   /                        \
  B           and            B
 /                            \
C                              C

But as ordered trees, these are the same. They've been displayed here as if they were binary trees (where each node has two children that may be empty subtrees). But with ordered trees, we just care that the root is the same and that the corresponding children are equal. So in the two cases above, the roots are both A. In both cases, the root has a single child B. And in both cases, that child has a single child C. So the trees are the same.

17,625