Assignment 6Binary TreesNO LATE ASSIGNMENTS WILL BE ACCEPTED FOR POINTS50 points

For this assignment, you will need to implement solutions to the following problems. Your solutions should be written (you can also use a drawing program if you wish as necessary). Show all work possible to ensure full credit -- this means that if you do not show your work, and your answer is correct, you still won't get full credit.

1. (10 points) Give upper and lower bounds on the number of leaves in a binary tree with N nodes. Be sure and justify your answer. It is permissible to give specific examples to help your justification.

2. (15 points) Draw the Binary Search Tree (BST) that results when you insert items with the keys: E A S Y Q U E S T I O N, in that order, into an initially empty binary tree. Refer to the algorithm on page 235 of your text if necessary.

3. (5 points) Given the following Huffman tree and encoded data, decode to produce the original text.

Encoded Data: 01110000000110111011100011111001010011000011000

4. (15 points) Given the following frequencies of characters, build a Huffman Tree using the algorithm discussed in class which uses two queues (which gives us O(n) time complexity )(NOTE: our algorithm comes from Wikipedia - http://en.wikipedia.org/wiki/Huffman_coding). When examining the two smallest items dequeued (based on the algorithm from Wikipedia), attach the smaller of the two as the left child of the internal node you are building. When two nodes have the same frequency, attach the least complex (a leaf node is less complex than an internal node; an internal node with two children is less complex than an internal node with more than two children) of the two nodes as the left child of the internal node you are building. Should two nodes have the same frequency and the same complexity, attach the one from the first queue as the left child of the internal node you are building. Show all work possible for full credit.

A: 10

E: 8

N: 6

T: 5

L: 4

U: 3

O: 3

P: 2

C: 1

5. (5 points) Encode the word "CANTALOUPE" based on the tree you built in problem 4.

To Turn In

·  A .pdf file with your solutions to the above problems. Name your file with your last name, followed by first initial, followed by hw6 (e.g. capaulthw6.pdf). Also include your name at the top of your solution.