This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Create a linked list for each level of a binary tree.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

Is this a binary search tree?
- Yes
Can we assume we already have a Node class with an insert method?
- 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]]

Algorithm

We can use either a depth-first or a breadth-first search. Intuitively, it seems like a breadth-first search might be a better fit as we are creating a linked list for each level.

We can use a modified breadth-first search that keeps track of parents as we build the linked list for the current level.

Append the root to the current level's linked list current
While the current is not empty:
- Add current to results
- Set parents to current to prepare to go one level deeper
- Clear current so it can hold the next level
- For each parent in parents, add the children to current
Return the results

Complexity:

Time: O(n)
Space: O(n)

Code



In [1]:

    
%run ../bst/bst.py



In [2]:

    
def create_level_lists(root):
    if root is None:
        return
    results = []
    current = []
    parents = []
    current.append(root)
    while current:
        results.append(current)
        parents = list(current)
        current = []
        for parent in parents:
            if parent.left is not None:
                current.append(parent.left)
            if parent.right is not None:
                current.append(parent.right)
    return results

Unit Test



In [3]:

    
%run ../utils/results.py



In [4]:

    
%%writefile test_tree_level_lists.py
from nose.tools import assert_equal


class TestTreeLevelLists(object):

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

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

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

        print('Success: test_tree_level_lists')


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


if __name__ == '__main__':
    main()









    



Overwriting test_tree_level_lists.py



In [5]:

    
%run -i test_tree_level_lists.py









    



Success: test_tree_level_lists