Breadth-First Traversal of a Binary Tree

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:

  1. Investigate how to use Python to create a binary tree data structure,
  2. Use our binary tree data structure to initialise different binary trees,
  3. 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.

#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

Binary Tree #1Binary Tree #2Binary Tree #3

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

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:
  • 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.

Did you like this challenge?

Click on a star to rate it!

Average rating 4.2 / 5. Vote count: 15

No votes so far! Be the first to rate this post.

As you found this challenge interesting...

Follow us on social media!