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
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 . 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*.