Question

how many binary trees (with unlabeled nodes) of height 2 are there? hint: count the number where the root only has a left child, followed by only a right child, and followed by both a left and a right child. then add these three numbers.

Answer 1

There are 4 binary trees of height 2.

Step-by-step explanation:

In order to determine the number of binary trees of height 2, we need to consider three cases: when the root only has a left child, when the root only has a right child, and when the root has both a left and a right child.

Case 1: Only a left child - In this case, there is only one possible binary tree.

Case 2: Only a right child - Similarly, there is only one possible binary tree.

Case 3: Both a left and a right child - For this case, we can consider it as two separate binary trees of height 1 attached to the root, which gives us a total of 2 possibilities.

Adding up the number of possibilities for each case, we have 1 + 1 + 2 = 4 binary trees of height 2.

Answer 2

The number of binary trees of height 2 is 3.

Step-by-step explanation:

To determine the number of binary trees of height 2, we can consider the different cases for the root of the tree.

Case 1: The root only has a left child. In this case, the left child can have a height of 1 and the right child can have a height of 0. There is only one possible binary tree in this case.

Case 2: The root only has a right child. In this case, the left child can have a height of 0 and the right child can have a height of 1. There is only one possible binary tree in this case.

Case 3: The root has both a left and a right child. In this case, the left child and the right child can both have a height of 1. There is only one possible binary tree in this case.

Therefore, the total number of binary trees of height 2 is 1 + 1 + 1 = 3.