CS130 N

DATA STRUCTURES

Work Sheet 4

1.

Prove correctness of Huffman's algorithm for constructing optimal prefix free codes.

2.

Determine if every binary tree is uniquely identified by

(i) Preorder and Inorder traversals.

(ii) Preorder and Postorder traversals.

3.

Show that the number of distinct permutations of $1 , 2, \ldots n$ achievable by a stack is equal to the number of binary trees with n nodes.

4.

The level listing of a tree lists all the nodes in a tree in order of their levels (no. of links from the root), i.e. nodes at level $1 , 2 \ldots$. Describe an algorithm to list the nodes of a tree in order of their level number.

5.

Write an algorithm to swap the left and right children of every node in a binary tree.

6.

Write an algorithm to insert a new node t as the left child of node s in a threaded binary tree. The left pointer of s becomes the left pointer of t.