HW8 SAMPLE ANSWERS

1. (a) preorder  ABDGICEHJKF
       inorder   BIGDAEJHKCF
       postorder IGDBJKHEFCA
   (b) Based on the preorder, the root must be C. Using the inorder
       this exposes the nodes in the left and right subtrees:
       AIDBKHM C FEJNLOG
       Repeat recursively.
       You get this final tree:
                              C
                            /   \
                          A       E
                           \     / \
                            B   F   G
                           / \     /
                          D   H   J
                         /   / \   \
                        I   K   M   L
                                   / \ 
                                  N   O
        Postorder traversal:
        IDKMHBAFNOLJGEC

2.  

public void mirror() {
        swapChildren(root);
}

private void mirror(BTNode<E> localRoot) {
        if (localRoot == null) return;
        mirror(myRoot.left);
        mirror(myRoot.right);
        BTNode<E> temp = localRoot.right;
        localRoot.right = localRoot.left;
        localRoot.left = temp;
}

3. (a)  2^(i-1)     (where ^ means exponentiation)          <<< CORRECTION!
   (b)  1 + 2 + 4 + ... + 2^(n-2) + 2^(n-1) = 2^n - 1       <<< CORRECTION!
   (c)  Total number of nodes in a tree with n levels:
        1 + 2 + 4 + ... + 2^(n-2) + 2^(n-1)                 <<< CORRECTION!
        The last term in the sum is the number of leaves.
        By part (b), the other terms must add up to 2^(n-1) - 1.  << CORRECTION!
        Thus, the number of leaves is 1 more than the number of nonleaves.

4.

public E getMinimum() {
       if (root == null) return null;
       return getMinimum(root);
}

private E getMinimum(BTNode<E> localRoot) {
       // Precondition: localRoot is not null
       if (localRoot.left == null)
              return localRoot.data;
       return getMinimum(localRoot.left);
}

5. 

public E getMinimum() {
       if (root == null) return null;
       BTNode<E> nodeRef = root;
       while (nodeRef.left != null) {
              nodeRef = nodeRef.left;
       }
       return nodeRef.data;
}

6. 

Operation   Balanced BST            Non-balanced BST
Traverse    O(n)                    O(n)
Find        O(log n)                O(n)
Add         O(log n)                O(n)
Remove      O(log n)                O(n)

7. 

public E find(E target) {
        if (root == null) return null;
        BTNode<E> nodeRef = root;
        while (nodeRef != null) {
                int compResult = target.compareTo(nodeRef.data);
                if (compResult == 0)
                        return nodeRef.data;
                else if (compResult < 0)
                        nodeRef = nodeRef.left;
                else    // compResult > 0
                        nodeRef = nodeRef.right;
        }
        return null;    // if we reach here, target is not found
}

8.

(a)  Tree: 

                         42
                      /      \
                   12          53
                 /    \           \
               8       16           60
             /           \         /  
           2              22     57   
                         /
                       19

     Recursive Calls (node<X> means the node with the value X):
     remove (node<42>, 65)
     remove (node<53>, 65)
     remove (node<60>, 65)            
     remove (node<65>, 65) returns null
     (all other calls return a reference to the given node)

(b)  Tree: 

                         42
                      /      \
                   12          53
                 /    \           \
               8       22           60
             /        /            /  \
           2        19           57    65

     Recursive Calls (node<X> means the node with the value X):
     remove (node<42>, 16)
     remove (node<12>, 16)
     remove (node<16>, 16) returns node<22> which gets stored as new right child of node<12>
     (all other calls return a reference to the given node)

(c)  Tree: 

                         42
                      /      \
                    8          53
                 /    \           \
               2       16           60
                         \         /  \
                          22     57    65
                         /
                       19

     Recursive Calls (node<X> means the node with the value X):
     remove (node<42>, 42) 
     remove (node<12>, 12) 
     Since node has two children, code calls helper method that
     goes to left child and searches for rightmost node.
     Since left child IS the rightmost node of left subtree,
     helper returns node<8> which gets patched in as new left child
     of 42.
     (all other calls return a reference to the given node)

(d)  Tree: 

                         22
                      /      \
                   12          53
                 /    \           \
               8       16           60
             /           \         /  \
           2              19     57    65

     Recursive Calls (node<X> means the node with the value X):
     remove (node<42>, 42)
     Since node has two children, code calls helper method with
     left child to find rightmost node of left subtree (node<22>).
     Since this node has a left child (node<19>), this reference
     is returned to the previous recursive call to reset the 
     right link of 16 to 19. Other returns from the helper method
     do not change the tree. The final returned value from the
     series of helper method calls is stored as the new data value
     of the removed node.