Homework 9: Chapter 7 Homework Solutions


Click here for some solutions

Due Thu Apr 3, 9:55 AM

Do the following exercises from Chapters 7(4th Edition):
R-7.7, R-7.10, R-7.11, R-7.12, R-7.14, and R-7.25. For 7.25, in addition to drawing the expression tree, translate the infix expression into prefix and postfix notation by performing preorder and postorder traversals respectively.

R-7.7. What is the running time of height2(T,v) in code fragment 7.6 when called on a node v distinct from the root.

The running time is Big-O(nv), where nv is the number of nodes in the subtree rooted at node v.

R-7.10. Draw an expression tree with 4 external nodes storing 1, 5, 6,7 so that the value of the root is 21.

The tree expresses the formula: (6/(1 - (5/7))).

R-7.11. For a ordered tree T with more than one node, is it possible that the preorder and postorder traversals visit the nodes in the same order? And is it possible for preorder to visit the nodes in the reverse order of postorder?

It is not possible for the postorder and preorder traversal of a tree with more than one node to visit the nodes in the same order. A preorder traversal will always visit the root node first, while a postorder traversal node will always visit an external node first.

Yes, it is possible for tranversals to be in reverse order for a tree with two nodes.

R-7.12. Same as previous question for a proper binary tree.

Not possible for pre- and post-order traverals to visit the nodes in the same order.

Not possible for pre- and post-order traversals to visit nodes in the reverse order for a proper binary tree. For a T with left and right subtrees Tl and Tr, a postorder would visit the postorder of Tl, then postorder of Tr and then the root, while a preorder would visit the root and then the preorder of Tl and then the preorder of Tr. Clearly these traversals cannot be the reverse since in both cases all the nodes of Tl are visited before Tr

R-7.14.Draw a single binary tree that gives preorder EXAMFUN and inorder MAFXUEN. 

               E
             /   \
            X     N
          /  \
         A    U
        / \
       M   F

R-7.14.Draw the binary tree for (((5+2)*(2-1))/((2+9)+((7-2)-1))*8). 

                 / 
             /      \
            *         * 
          /  \       /   \
         +    -     +     8
        / \   /\   /  \ 
       5   2 2  1 +    -
                 / \  / \
                2   9 -  1
                     / \ 
                    7   2

Postfix:  5 2 + 2 1 - * 2 9 + 7 2 - 1 - + 8 * /
Prefix:  / * + 5 2 - 2 1 * + + 2 9 - - 7 2 1 8
Value:  7 / 120

How To Submit

  1. Bring your solutions to class. We'll go over the answers in class. Note: This assignment may be collected and graded.