Question

Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees. Let T(n) denote the number of binary trees with n nodes. For example T(3) 5 because there are five binary trees with three nodes: (a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for T(n). (8 marks) A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is a fully-internal node) or two empty children (i.e. is a leaf). (b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd number of nodes. (4 marks) (c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving T(n') where n' <n. Hint: Relate the internal nodes of a full binary tree to T(n). (4 marks)

Answer 1

(a)  Let us consider all the possible binary search trees with each element at the root. If there are n nodes, then for each choice of root node, there must be n – 1 non-root nodes and these non-root nodes must be partitioned into those that are less than a chosen root and those that are greater than the chosen root.

Let us assume, node i is chosen to be the root. Then there must be i – 1 nodes smaller than i and n – i nodes (derived from: (n-1)-(i-1)) bigger than i. For each of these two sets of nodes, there is a certain number of possible sub-trees.

Let T(n) be the total number of binary trees with n nodes. The total number of trees with i at the root is T(i – 1) × T(n – i). The two terms are multiplied together because the arrangements in the left and right sub-trees are independent. That is, for each arrangement in the left tree and for each arrangement in the right tree, you get one tree with i at the root.

Summing over i gives the total number of binary search trees with n nodes.

$T(n) = \sum_{i=1}^{n}T(i-1)T(n-i)$

The base case is T(0) = 1 and T(1) = 1, because there is one empty tree and there is one tree with one node.

(b) This can be proven using the style of induction proof where we reduce from an arbitrary instance of size n, to an instance of size n−1 that meets the induction hypothesis.

i. Base Cases: The non-empty tree with zero internal nodes has one leaf node. A full binary tree with one internal node has two leaf nodes. Thus, the base cases for n=0 and n=1 conform to the theorem.

ii. Induction Hypothesis: Assume that any full binary tree T containing n−1 internal nodes has n leaves.

iii. Induction Step: Given tree T with n internal nodes, select an internal node I whose children are both leaf nodes. Remove both of I's children, making II a leaf node. Lets call the new tree T′. So, T′ has n−1 internal nodes. From the induction hypothesis, T′ has n leaves. Now, restore I's two children. We once again have tree T with n internal nodes. Because T′ has n leaves, adding the two children yields n+2. However, node I counted as one of the leaves in T′ and has now become an internal node. Thus, tree T has n+1 leaf nodes and n internal nodes and the total number of nodes is 2n+1.

By mathematical induction the theorem holds for all values of n>0. Therefore, the total number of nodes in a full binary tree will always be odd.

(c) T(n) is the number of binary trees with n nodes, and also therefore the number of full trees with 2n`+1 nodes. The number of full binary trees with n nodes is therefore T((n-1)/2).

We can say that,

T(n`) = T((n-1)/2).   [Where $n` \leq n$ ]

Since you can't have half a node, the answer is 0 when n is even.