Problem 1:

Problem 2:

A binary tree is called an AVL tree if the subtrees of every node differ in height by at most 1. (Assume the height of an empty tree is “-1”.)

a. Show all AVL trees of height 0 and height 1, and show 6 AVL trees of height 2.

b. Let’s call an AVL tree left-minimal if the left subtree of every node has the minimum number of nodes possible while the tree remaining an AVL tree. Show all left-minimal AVL trees of height 0, height 1, height 2, and height 3.

c. Let N(h) be the number of nodes of a left-minimum AVL tree of height h. Express N(h) in terms of N(h − 1) and N(h − 2).

Problem 3:

a. Let T be a binary tree and assume that every node has one numerical data field (called “data”) of type double. Write a recursive algorithm that takes as input the tree T and computes the following values: (1) number of nodes in T, (2) the average value of the data fields of the nodes in T. Give the time complexity of your algorithm. Note: You should one single algorithm (not two separate algorithms) that computes both values together.

b. Write a recursive algorithm that takes as input a binary tree T and returns whether or not the tree is full. Give the time complexity of your algorithm.

(NOTE: Your grade in all the homework assignments and exams depends on the correctness and speed of your algorithms.)

Problem 4:

a. Build step by step a min-heap for 25, 11, 54, 35, 46, 5, 14, 65, 2, 59, 3 by inserting those elements (in order) into an initially empty heap. Show how the heap looks like (in a tree form and in an array form) after each insertion of the first 9 elements, then show the insertion of the last element (3) step by step in tree form and array form.

b. Perform delete-min() on the min-heap you built in part a. Show how the heap looks like (in a tree form and array form) after each step.

c. Insert 25, 11, 54, 35, 46, 5, 14, 65, 2, 59, 3, 12, 13, 7, 10, 18, 17, 15 (as you read them) into an originally empty binary search tree. Show how the tree looks like after each insertion. Perform delete (11) on this tree step by step, showing how the tree looks like after each step.

Problem 5:

Consider the elements 1, 2, ... , 11. Perform the following sequence of Unions (U) and Finds (F) using the path compression algorithm, show how the forest looks like after each operation, and display the PARENT array alongside each snapshot of the forest:

U(1,4) U(2,3) U(1,2) U(5,6) U(1,5) U(7,8) U(9,10) U(9,11) U(7,9) U(9,1) F(8)

(Tie-breaking note: in U(i,j), if the two trees rooted at i and j are of equal size, make i the root of the new tree.)

Bonus Problem: