READING for Week 8

Sedgewick, 217-223, 230-241, 477-508

---------------------------------------------

			 EXERCISES for Week 8

 1. Write a C program to print all the keys less than a given value v 
    in a binary search tree.

 2. Draw the binary tree representation described in Property 5.4 of the tree




 3. Give the inorder and postorder traversal for the tree whose preorder
    traversal is A B C - - D - - E - F - -.  The letters correspond to
    labelled internal nodes; the minus signs to external nodes.

 4. Sedgewick, Exercise 5.79

 5. Give the stack contents, in the style of Figure 5.27, for the
    preorder, inorder, and postorder traversals of the center tree
    in Exercise 5.79.

 6. Sedgewick, Exercise 12.27

 7. Sedgewick, Exercise 12.33

 8. Sedgewick, Exercise 12.44

 9. Sedgewick, Exercise 12.49

10. A binary tree is said to be "balanced" if the height of its left
    subtree differs from the height of its right subtree by at most 1.  
    Write a C program to determine if a given binary tree is balanced.  

---------------------------------------------

                    Answers to Exercises for Week 8

 1.
        void smaller(link tree, int v)
          {
            if ( tree == NULL ) return;
            smaller(tree->l);
            if ( tree->key >= v ) return; 
            printf("%d ", v);
            smaller(tree->r);
          }
 2.








 3. Inorder:      - C - B - D - A - E - F -
    Postorder:    - - C - - D B - - - F E A

 4.  
                      left              middle                right
    preorder      D B A C F E G        C B A D E        E D B A C H F G I
    inorder       A B C D E F G        A B C D E        A B C D E F G H I
    postorder     A C B E G F D        A B E D C        A B C D G F I H E 
    level-order   D B F A C E G        C B D A E        E D H B C F I A G

 5.       preorder        inorder        postorder
           C*              C*             C*
           C  B* D*        B* C  D*       B* D* C
           B* D*           A* B  C  D*    A* B  D* C
           B  A* D*        A  B  C  D*    A  B  D* C
           A* D*           B  C  D*       B  D* C
           A  D*           C  D*          D* C
           D*              D*             E* D  C
           D E*            D  E*          E  D  C 
           E*              E*             D  C
           E               E              C 

 6. S E A Y Q U T I O N

 7. 






 8. 







 9.      int searcheqR(link h, Key v)
          { Key t = key(h->item); int val = 0;
            if (h == z) return 0;
            if less(v, t) return searchR(h->l, v);
            else return searchR(h->r, v) + (eq(v, t) ? 1 : 0);
          }
        int STsearcheq(Key v) 
          { return searcheqR(head, v); } 

10. Apparantly, the height needs to be computed, at least until some
    unbalanced node is found.  So this routine returns the height, -1 if 
    the tree is not balanced.

        int balanced(link tree)
          {
            int bl, br;
            if ( tree == NULL ) return 0;
            bl = balanced(tree->l);
            br = balanced(tree->r);
            if (bl < 0 || br < 0) return -1;
            if (bl == br)     return bl + 1;
            if (bl == br + 1) return bl + 1;
            if (bl == br - 1) return br + 1;
            return -1;  
          }