This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Challenge Notebook¶

## Constraints¶

• Is this a binary search tree?
• Yes
• Should each level be a list of nodes?
• Yes
• Can we assume we already have a Node class with an insert method?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

• 5, 3, 8, 2, 4, 1, 7, 6, 9, 10, 11 -> [[5], [3, 8], [2, 4, 7, 9], [1, 6, 10], [11]]

Note: Each number in the result is actually a node containing the number

## Algorithm¶

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

## Code¶

In [ ]:
%run ../bst/bst.py

In [ ]:
class BstLevelLists(Bst):

def create_level_lists(self):
# TODO: Implement me
pass


## Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:
%run ../utils/results.py

In [ ]:
# %load test_tree_level_lists.py
import unittest

class TestTreeLevelLists(unittest.TestCase):

def test_tree_level_lists(self):
bst = BstLevelLists(Node(5))
bst.insert(3)
bst.insert(8)
bst.insert(2)
bst.insert(4)
bst.insert(1)
bst.insert(7)
bst.insert(6)
bst.insert(9)
bst.insert(10)
bst.insert(11)

levels = bst.create_level_lists()
results_list = []
for level in levels:
results = Results()
for node in level:
results_list.append(results)

self.assertEqual(str(results_list[0]), '[5]')
self.assertEqual(str(results_list[1]), '[3, 8]')
self.assertEqual(str(results_list[2]), '[2, 4, 7, 9]')
self.assertEqual(str(results_list[3]), '[1, 6, 10]')
self.assertEqual(str(results_list[4]), '[11]')

print('Success: test_tree_level_lists')

def main():
test = TestTreeLevelLists()
test.test_tree_level_lists()

if __name__ == '__main__':
main()


## Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.