CSC148 - Lab 6

Binary Search Tree Removal

For this part, you will write a few simple tests for the removal method we wrote in lecture. Download bst.py and write 3 tests for the removal method; one which removes a leaf, one which removes a node with one child, and one that removes a node with two children. Modify the in_order method to return a list of the elements instead of printing it out, and use that in your tests.

Level Order

In lecture, we discussed inorder, preorder and postorder traversals. For this exercise you will implement a new traversal of a binary tree called level order.
Essentially, you want to ouput the nodes according to increasing depth, and nodes at the same depth are output left to right. Consider, for example, the following binary tree: 
            A
           / \
          /   \
         B     C
        / \     \
       D   E     F
                / \
               /   \
              G     H
From left to right, the nodes at depth 0 are A, depth 1 are B and C, at depth 2 are D, E and F, and finally at depth 3 are G and H. So the level order traversal of this tree is A,B,C,D,E,F,G,H.
Add a method level_order to the Binary Search Tree in bst.py to return a list of the values stored on the nodes in level order. Write a few simple tests for you code.
Hint: One way to do this is to use a queue, and add nodes to at in an appropriate way.