<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Solution Notebook  Problem: Implement breadth-first search on a binary tree.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)  Constraints* Can we assume we already have a Node class with an insert method?    * Yes  Test Cases Breadth-First Search* 5, 2, 8, 1, 3 -> 5, 2, 8, 1, 3  Algorithm* Initialize queue with root* While queue is not empty    * Dequeue and print the node    * Queue the left child    * Queue the right childComplexity:* Time: O(n)* Space: O(n)  Code<jupyter_code>%run ../bst/bst.py
from collections import deque


def bfs(root, visit_func):
    queue = deque()
    queue.append(root)
    while queue:
        node = queue.popleft()
        visit_func(node)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)<jupyter_output><empty_output><jupyter_text>Unit Test<jupyter_code>%run ../utils/results.py
%%writefile test_bfs.py
from nose.tools import assert_equal


class TestBfs(object):

    def __init__(self):
        self.results = Results()

    def test_bfs(self):
        node = Node(5)
        insert(node, 2)
        insert(node, 8)
        insert(node, 1)
        insert(node, 3)
        bfs(node, self.results.add_result)
        assert_equal(str(self.results), '[5, 2, 8, 1, 3]')

        print('Success: test_bfs')


def main():
    test = TestBfs()
    test.test_bfs()


if __name__ == '__main__':
    main()
%run -i test_bfs.py<jupyter_output>Success: test_bfs
{'fraction_non_alphanumeric': 0.12364672364672365, 'fraction_numerical': 0.011396011396011397, 'mean_word_length': 3.2829268292682925, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 10, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '243911', 'license': 'Apache-2.0', 'n_tokens_mistral': 608, 'n_tokens_neox': 569, 'n_words': 164, 'path': 'graphs_trees/tree_bfs/bfs_solution.ipynb', 'repo_name': 'filippovitale/interactive-coding-challenges', 'size': '1761'}