Mathematical Properties of Binary Trees

-----------

Show that if binary tree T is full at level i, then it is full at every level j smaller than i.

---------------

Show that the depth of the complete binary tree Tn for a general n is given by
D(Tn) = [log2n].

See attached for better format.

------------

Using induction, give a direct proof of Proposition 4.2.3 without using the transformation to 2-trees.
Proposition 4.2.3
Suppose T is any 2-tree. Then the number of leaf nodes is 1 greater than the number of internal nodes of T; that is,
I(T) = L(T) – 1.
Equivalently, we have
n(T) = 2L(T) – 1.

----------

Prove Proposition 4.2.5
Proposition 4.2.5
Suppose T is a 2-tree. Then T is full at the second deepest level if and only if all the leaf nodes are contained in two levels (d – 1 and d).

-------------

Textbook: Algorithms: Sequential, Parallel, and Distributed by Kenneth Berman and Jerome Paul

Attached file(s):

Show that the depth of the.doc  View File