import unittest
from binarysearchtree import Node, BinarySearchTree
from random import seed, sample
from main import main as mn
from recursioncounter import RecursionCounter as rc
import io
import sys

class TestNode(unittest.TestCase):
def test_node_creation(self):
   node = Node(12345)
   self.assertTrue(node.is_leaf())
   self.assertEqual(node.data, 12345)
   self.assertEqual(node.height, 0)
   node.update_height()
   self.assertEqual(node.height, 0)

class TestBinarySearchTree(unittest.TestCase):
def test_tree_creation(self):
   bst = BinarySearchTree()
   self.assertEqual(len(bst), 0)
   self.assertTrue(bst.is_empty())

def test_tree_size(self):
   bst = BinarySearchTree()
   seed(0)
   data = sample(range(1, 400), k=123)
   for datum in data:
         bst.add(datum)
   self.assertEqual(len(bst), 123)

def test_tree_height(self):
   bst = BinarySearchTree()
   bst.add(123)
   self.assertEqual(bst.height(), 0)
   bst.add(12)
   bst.add(2)
   self.assertEqual(bst.height(), 2)

def test_find(self):
   bst = BinarySearchTree()
   seed(0)
   data = sample(range(1, 400), k=123)
   for datum in data:
         bst.add(datum)
   self.assertEqual(bst.find(data[0]).data, data[0])
   self.assertEqual(bst.find(401), None)

def test_remove(self):
   bst = BinarySearchTree()
   seed(0)
   data = sample(range(1, 100), k=10)
   for datum in data:
         bst.add(datum)
   bst.remove(data[0])
   self.assertEqual(bst.find(data[0]), None)

def test_preorder(self):
   bst = BinarySearchTree()
   seed(0)
   data = sample(range(1, 400), k=123)
   for datum in data:
         bst.add(datum)
21, 9, 4, 2, 3, 7, 14, 10, 18, 15, 26, 30, 28,
21 (4)
9 (3)
4 (2)
2 (1)
[Empty]
3 (0) [leaf]
7 (0) [leaf]
14 (2)
10 (0) [leaf]
18 (1)
15 (0) [leaf]
[Empty]
26 (2)
[Empty]
30 (1)
28 (0) [leaf]
[Empty]
26 (3)
10 (2)
2 (1)
[Empty]
3 (0) [leaf]
14 (0) [leaf]
30 (1)
28 (0) [leaf]
[Empty]
Figure 1. Example output showing preorder traversal and printing the tree.
Test Cases
Following is the set of assertion-based - test cases that your program must pass, and by
which your code will be graded. You will be given the pytest unit test code to run against
your
code
as
you
develop
it.
This
allows
you
to
learn
how
test
are
written,
and
to
know
what
your score is going to be when the code is graded before you submit it
Test Empty BST
Create an empty BST
assert size == 0 assertis_empty is True
Test Size
Create an empty tree
seed random number generator with 0
Insert 123 random integers in range 1, 400 into the tree assert size == 123
Test Height
Create an empty tree Insert value 123 into the tree
assert height =: 0
Insert 12 and 2 into the tree
assert height =: 1
Test Insert and Find
Create an empty tree
seed random number generator with 0
Generate a list of 123 random integers in range 1, 400
Insert each integer into the list in the order they appear in the list above
assert find (first item in list) =: first item in list
assert find(401) == None
Test Remove
Create an empty tree
seed random number generator with 0
Generate a list of 10 random integers in range 1, 100
Insert each integer into the list in the order they appear in the list above
remove (first item in list)
assert find 1(first item in list) == None
Test Preorder Traversal
Create an empty tree
seed random number generator with 0
Generate a list of 123 random integers in range 1, 400
Insert them in the list in the order they appear in the list above
assert returned value is a list of length 123
do preorder traversal assert that the first element of the random integers is the first
element of the returned list
Test String
Implement scenario given in Figure 1 and implemented in the main program, but as a test
case.
Test Recursion
the following functions will be tested to verify that they use recursion to do their work
add
find
remove
preorder
_str
__len__
(remember to have the line RecursionCounter 0 at the beginning of every recursive helper
function)
Test Code Quality
PyLint will be run on main.py and binarysearchtree.py. Both must have at least an 8.5
PyLint score.
Grading (100 points)
Passes TestNode
10
Passed TestBinarySearchTre
35
Passed RecursionTests
30
passed Coding Standards
25
Turn in to Canvas:
main.py
binarysearchtree.py

Problem 1 1. T(n) = 9T(n/3) + n + n 2 + 1 2. T(n) = 2T(2n/9) + â...