Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Level-Order Traversal

Explore level-order traversal in binary trees, understand the algorithm using a queue, and implement it in Python. Learn to handle nodes level-by-level and enhance your binary tree traversal skills.

We'll cover the following...

In this lesson, we go over how to perform a level-order traversal in a binary tree. We then code a solution in Python building upon our binary tree class.

Here is an example of a level-order traversal:

Algorithm

To do a level-order traversal of a binary tree, we require a queue. Have a look at the slides below for the algorithm:

Implementation

Now that you are familiar with the algorithm, let’s jump to the implementation in Python. First, we’ll need to implement Queue so that we can use its object in our solution of level-order traversal.

Python 3.5
class Queue(object):
  def __init__(self):
    self.items = []
  def enqueue(self, item):
    self.items.insert(0, item)
  def dequeue(self):
    if not self.is_empty():
      return self.items.pop()
  def is_empty(self):
    return len(self.items) == 0
  def peek(self):
    if not self.is_empty():
      return self.items[-1].value
  def __len__(self):
    return self.size()
  def size(self):
    return len(self.items)

The constructor of the Queue class initializes self.items to an empty list on line 3. This list will store all the elements in the ...