test-bst.py :

#!/usr/bin/python import unittest import bstselect

class TestBST(unittest.TestCase): def setUp(self): pass def test(self): t = bstselect.BST() t.insert(0) t.insert(10) t.insert(5)

ans = t.select(1) self.assertEqual(ans.key, 0) ans = t.select(2) self.assertEqual(ans.key, 5) ans = t.select(3) self.assertEqual(ans.key, 10)

ans = t.select(0) self.assertEqual(ans, None) ans = t.select(4) self.assertEqual(ans, None)

t.insert(6) t.insert(8) t.insert(7) ans = t.select(4) self.assertEqual(ans.key, 7)

if __name__ == '__main__': suite = unittest.TestLoader().loadTestsFromTestCase(TestBST) unittest.TextTestRunner(verbosity=2).run(suite) bstselect.py :

import bstsize

class BST(bstsize.BST): """ Adds select method to BST, starting with code from bstsize. """ def select(self, index): """ Takes a 1-based index, and returns the element at that index, or None if the index is out-of-bounds. Starting at the root, the tree is searched by examining the size of the left-child tree, which gives the number of elements smaller than the current node. """

1. (12 points) select in Binary Search Trees Implement select in bstselect.py. select takes an index, and returns the element at that index, as if the BST were an array. select is essentially the inverse of rank, which took a key and returned the number of elements smaller than or equal to that key. The index for select should be 1-based (not 0-based like Python often uses). Download ps2-bst.zip. Read test-bst.py to clarify how select should work. Put your code in bstselect.py until test-bst.py works. Be sure to comment your code, explaining your algorithm. Submit bstselect.py to the class website