Homework 3 (Cpt S 223)Due Date:October 8, 2010Total points:471. (3 points)Give the expression tree for (a+ ( b-c)*(d*e)-f)*(g+h-i).2. (10 points)ABCF IGH KJL MD EFor the above shown tree, answer the following:a) Height of the tree = ?b) Depth of node J = ?c) Height of node J = ?d) Redraw the tree by the First-child, Next-Sibling method.e) Give the post-o r der, pre-order and in-order traversals of the tree.13. (6 points)Just given the pre-order and in-o r der traversals of a tree, one can reconstruct thetree. To illustrate this capability, draw the tree by reconstructing it from the followingtraversals:Pre-order traversal is: a, f, e, d, g, h, c; andIn-order traversal is: e, f, g, d, h, a, c.(Note: nodes are labeled by alphabets.)4. (7 points)a) Draw the final BSTs that result from the following two different insertion sequencesof the same set of elements:a) Insertion sequence: 8 7 1 6 2 3 5 4b) Insertion sequence: 5 7 3 2 8 6 4 1For both cases, start with an empty tree.b) Briefly state what is so markedly different between these two resulting BSTs con-structed over the same set of elements but with just different insertion sequences.5. (5 points)Starting with an empty tree T0, show the set of BSTs T0⇒ T1⇒ T2⇒ . . . resultingfrom performing the following sequence of operations (in that order): Insert(5), In-sert(10), Insert(2), Insert(7), Insert(8), Remove(5).PS: you need to show the tree resulting after each insertion or removal operation.6. (8 points)Starting with an empty tree T0, show the set of AVL trees T0⇒ T1⇒ T2⇒ . . . re-sulting from performing the f ollowing sequence of operations (in that order): Insert(7),Insert(5), Insert(2), Insert(4), Insert(3), Insert(1). If at any step you need to rebalancethe tree using rotation, then clearly identify: i) the node that has the imbalance, and2ii) the corresponding rotation “case” that applies there (i.e., case 1 or 2 or 3 or 4).7. (8 points)Exercise 4.19. (Weiss, page 177). Follow t he same instructions a s outlined for
View Full Document