test.py

    def test_remove(self):
        self.tree = self.build_big_tree()
        expected = [ 6, 8, 9, 10, 11, 12, 14, 20, 27, 28 ]

        # ensure it starts out as intended. this should always pass
        actual = []
        self.private_inorder_fetch(self.tree.root_node, actual)
        self.assertEqual(expected, actual, "Initial tree was malformed. Our fault, not yours")

        # remove the top node, 20
        self.tree.remove(20)
        expected.remove(20)
        actual = []
        self.private_inorder_fetch(self.tree.root_node, actual)
        self.assertEqual(expected, actual, "Removing top node (20) did not work")

        # remove a leaf, 9
        self.tree.remove(9)
        expected.remove(9)
        actual = []
        self.private_inorder_fetch(self.tree.root_node, actual)
        self.assertEqual(expected, actual, "Removing leaf node (9) did not work") 
        
        # remove a middle node, 27
        self.tree.remove(27)
        expected.remove(27)
        actual = []
        self.private_inorder_fetch(self.tree.root_node, actual)
        self.assertEqual(expected, actual, "Removing middle node (27) did not work") 

    def build_big_tree(self):
        # from Peyman:
        # remove does not work for the following example if I want to remove 20
        #                    20
        #                  /    \
        #               10       27
        #              /   \      \
        #           8       12     28
        #        /   \     /  \
        #      6      9   11   14
        # inorder starts out as:
        # [ 6, 8, 9, 10, 11, 12, 14, 20, 27, 28 ]
        top = self.mknode(20)
        top.left = self.mknode(10)
        top.left.left = self.mknode(8)
        top.left.left.left = self.mknode(6)
        top.left.left.right = self.mknode(9)
        top.left.right = self.mknode(12)
        top.left.right.left = self.mknode(11)
        top.left.right.right = self.mknode(14)
        top.right = self.mknode(27)
        top.right.right = self.mknode(28)
        ret = BinarySearchTree()
        ret.root_node = top
        return ret

    def private_inorder_fetch(self, node, numbers):
        if node is None:
            return
        else:
            self.private_inorder_fetch(node.left, numbers)
            numbers.append(node.data)
            self.private_inorder_fetch(node.right, numbers)