Data Structures and Algorithms in Python/

...

/

Level-Order Traversal

Level-Order Traversal

In this lesson, you will learn how to implement level-order traversal of a binary tree in Python.

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.

Press + to interact
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 queue. ...