** Next:** 4.8.2 Binary Search Trees
** Up:** 4.8 Problems
** Previous:** 4.8 Problems

- 1.
- Show in any binary tree that the number of leaves is one more than
the number of nodes of degree two.
- 2.
- The degree of a node in a tree is the number of children the node
has. If a tree has
*n*_{1} nodes of degree 1, *n*_{2} nodes of degree 2, ...,
*n*_{m} nodes of degree *m*, compute the number of leaves in the tree in
terms of
*n*_{1}, *n*_{2},..., *n*_{m}.
- 3.
- Show that if T is a k-ary tree with
*n* nodes, each having a
fixed size, then *nk* + 1 - *n* of the *nk* link fields are null links (*n*
1).
- 4.
- Provide an efficient
*O*(*n*) time algorithm to determine the height
of a tree containing *n* nodes, represented using parent links.
You may build any other supporting data structures, if needed.
- 5.
- Associate a weight
*w*(*x*) = 2^{-d} with each leaf *x* of depth *d* in a binary tree *T*. Show that
*w*(

*x*)

1

where the sum is taken over all leaves *x* in *T*.

- 6.
- Consider a complete binary tree with an odd number of nodes.
Let
*n* be the number of internal nodes (non-leaves) in the tree.
Define the internal path length, *I*, as the sum, taken over
all the internal nodes of the tree, of the depth of each node.
Likewise, define the external pathlength, *E*, as the sum, taken over
all the leaves of the tree, of the depth of each leaf.
Show that *E* = *I* + 2*n*.
- 7.
- What is the optimal Huffman code for the following set of frequencies,
based on the first 8 Fibonacci numbers?
a |
b |
c |
d |
e |
f |
g |
h |

1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |

Write down the resulting Huffman tree.
Can you generalize your answer to find the optimal code when the
frequencies are the first *n* Fibonacci numbers?

** Next:** 4.8.2 Binary Search Trees
** Up:** 4.8 Problems
** Previous:** 4.8 Problems
eEL,CSA_Dept,IISc,Bangalore