A **tree** is a complex data structure used to store data (**nodes**) in a **“parent/child” relationship**. The top node of a tree (the node with no parent) is called the **root**. Each node of a tree can have 0, 1 or several **child nodes**. In a **Binary Tree**, each node can have a maximum of two child nodes.

The **Breadth-First Traversal** of a tree is used to read all the values of a tree, **one level at a time**, from the top level (root node) to the bottom level:

In this blog post will first:

- Investigate how to use Python to create a binary tree data structure,
- Use our binary tree data structure to initialise different binary trees,
- Use an algorithm to implement a breadth-first traversal of our tree,

#### Using a Node Class to create a Binary Tree

The following Python code is all what’s needed to create a Node/Tree structure.

1 2 3 4 5 6 |
#A class to implement a Node / Tree class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right |

#### Initialising the values of a Binary Tree

In order to initialise the above Binary Tree (Tree #1) we will need the following Python code:

1 2 3 4 5 6 7 8 9 10 11 12 |
tree = Node(47) #The root node of our binary tree tree.left = Node(36) tree.right = Node(66) tree.left.left = Node(25) tree.left.right = Node(39) tree.left.right.left = Node(38) tree.left.right.right = Node(42) tree.right.left = Node(63) tree.right.left.right = Node(64) tree.right.right = Node(68) |

Note that we have included other trees (#2 and #3) for you to initialise in Python for testing purposes.

#### Breadth-First Traversal of a Binary Tree

In order to implement a Breadth-First Traversal of a Binary Tree, we will need to use a **queue** data structure and we will base our algorithm on the following steps:

- Initialise the queue by enqueuing the root node of the tree to traverse
- While the queue is not empty:
- Dequeue a node from the queue,
- Output the value of this node,
- Enqueue the left and right node of this node to the queue.

In Python, a **queue** can be implemented as a simple **list**:

- Enqueuing an element to a list is done using the following instruction:
*list.append(element)* - Dequeuing an element from a list is done by removing its first element using the following instruction:

*node = list.pop(0)* - Checking if a queue is empty can be done by checking if the length of the list is equal to 0:

*if len(list)==0:*

#### Full Python code for the Breadth-First Traversal of a Binary Tree

#### Your Task:

Tweak the above code to perform a breadth-first traversal of the two other binary trees provided in the above tabs.