Question

Prove that a binary tree with n internal nodes has (n + 1) external nodes

Answer 1

: The proof is by induction on n ≥ 1. For n = 1, a binary tree consisting

of the root alone is a proper binary tree with an odd number of nodes

(namely, one). Thus the result holds for n = 1.

We use the so called course of values induction hypothesis: Assume that

for all proper binary trees with k nodes where 1 ≤ k < n that k is odd.

With this assumption, we wish to prove that the result holds for an arbitrary

(proper) binary tree T with n > 1 nodes. First note that n must be

at least 3 because there are no proper binary trees with 2 nodes. Furthermore

any proper binary tree with 3 or more nodes must have a root with

non-empty left and right subtrees. So T must have at least three nodes

and have non-empty left and right subtrees, TL and TR respectively, each

of which has < n nodes. Each node of TL and TR has zero or two children

since they are a part of the original proper binary tree T. Thus TL and

TR are proper binary trees. By the induction hypothesis each has an odd

number of nodes. Let 2k + 1, k ≥ 0, be the number of nodes of TL and

2m + 1, m ≥ 0, be the number of nodes of TR. Then the number of nodes

of T is 2(k + m) + 2 plus the root, or a total of 2(k + m) + 3, an odd

number.

Answer 2

An extended binary tree with n internal nodes has n+1 external nodes.

Proof by:

X(n) := number of external nodes in binary tree with n internal nodes.

Base case: X(0) = 1 = n + 1.

Induction step: Suppose theorem is true for all i < n. Because n ≥ 1, we have:

X(n) = X(k) + X(n-k-1)

= k+1 + n-k-1 + 1

= n + 1 proved that.

• Every node has 2 children pointers, for a total of 2n pointers.
• Every node except the root has a parent, for a total of n - 1 nodes with parents.
• These n - 1 parented nodes are all children, and each takes up 1 child pointer.
• Thus, there are n + 1 null pointers.
• Every null pointer corresponds to one external node by construction.

#SPJ3