Problem Set Answers: Trees

1. preorder: M G D A H K L T R V U W
   inorder: A D H G K L M R U V T W
   postorder: A H D L K G U V R W T M
   
   
2. No, it's not a BST. There are several places where the BST property is violated: H > G but H is in the left subtree of G, and U > T and V > T but both are in the left subtree of T
   
   
3. No it's not balanced, the problems are at the nodes containing T and R.
4. The level of G is 1, the level of W is 2, and the level of U is 4.
5. The height of the tree is 4.
6. The tree is out of balance at W.
7. The subtree rooted at G has height 3.
8. The level of O is 4. The level of J is 3.
9. 
   

10. preorder:   75 55 20 12 66 62 58 70 95 80 77 88 85 92 99 100
    inorder:    12 20 55 58 62 66 70 75 77 80 85 88 92 95 99 100
    postorder:  12 20 58 62 70 66 55 77 85 92 88 80 100 99 95 75
    

11. Yes, it is a BST.

12. 

    

    

    

    

    

13. 1. 
       
    2. 
       
    3. 
       
    4. 
       

14. 1. 

    2. 

    3. 

15. 1. possible
    2. not possible
    3. not possible
    4. possible
16. 1. possible
    2. not possible
    3. possible
    4. not possible

17. public int numNodes() {
       return numNodes(root);
    }
    private int numNodes(BSTNode<T> node) {
       if (node == null)
          return 0;
       else
          return 1 + numNodes(node.getLeft()) + numNodes(node.getRight());
    }
    
    

18. public int height() {
       return height(root);
    }
    private int height(BSTNode<T> node) {
       if (node == null)
          return 0;
       else {
          int hleft = height(node.getLeft());
          int hright = height(node.getRight());
          if (hleft > hright)
             return 1 + hleft;
          else
             return 1 + hright;
       }
    }
    
    

19. public T maxValue() {
       return maxValue(root);
    }
    private T maxValue(BSTNode<T> node) {
       if (node.getRight() == null)
          return node.item;
       else
          return maxValue(node.getRight());
    }
    
    

20. public void revOrder() {
       revOrder(root);
    }
    private void revOrder(BSTNode<T> node) {
       if (node != null) {
          revOrder(node.getRight());
          System.out.println(node.item);
          revOrder(node.getLeft());
    }
    
    

21. public void BSTPrint(BinarySearchTree<Pet> bst) {
       int i;
       Pet item;
       Iterator<Pet> bstIter = bst.iterator();
       while (bstIter.hasNext()) {
          item = bstIter.next();
          System.out.println(item);
       }
    }
    
    

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2016