In the prior script, we created a class Tree_Node and a method breadth_first_search(). The Tree_Node class contains the value of the root node and the list of child nodes.

The breadth_first_search() method implements steps 1 through 3, as explained in the theory section. You simply have to pass the root node to this method and it will traverse the tree using BFS.

Let's now create a tree with the tree that we saw in the diagram.

1// edges = [1, 2], [1, 5], [2, 3], [2, 5], [3, 4], [4, 5], [4, 6]
2addEdge(1, 2);
3addEdge(1, 5);
4addEdge(2, 3);
5addEdge(2, 5);
6addEdge(3, 4);
7addEdge(4, 5);
8addEdge(4, 6);