What is the number of possible ordered trees with 3 nodes A, B, C ?

The number of possible ordered trees with 3 nodes A, B, C is:
(a) 16     (b) 12
(c) 6       (d) 10

Also explain what are ordered trees?

4Comments
Sumit Verma @sumitkgp
5 Jul 2017 02:03 pm

Ordered trees are the binary tree having some labels on the nodes.

Consider 2 nodes.

For unordered trees, you can make only two structure of trees.

(Root + left child) or (Root + right child)

Now consider Ordered trees case,

Suppose we label nodes as A,B.

Now in the two possible structures we can put A and B in 4 ways.

1. A(root) + B(left child)

2. A(root) + B ( right child)

3. B(root) + A( left child)

4. B(root) + A(right child)

I hope got the difference.

pragya goyal @pragya
5 Jul 2017 05:53 pm

@sumitverma so the answer for this question would be 24???

Sumit Verma @sumitkgp
5 Jul 2017 11:04 pm

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.

Divya Kathuria @divyakathuria05
6 Jul 2017 09:41 am

In second case N=2, wont we get T(2)=4 considering the following:

1. A(root) + B(left child)

2. A(root) + B ( right child)

3. B(root) + A( left child)

4. B(root) + A(right child)

Please tell me where am I wrong?