Discover data structures and algorithms using Python. Gain insights into solving real-world problems and typical interview questions with detailed reviews, explanations, and hands-on coding exercises.

Data structures and algorithms are among the most fundamental concepts of Computer Science. Whether it’s real-world problems you’re trying to solve or the typical coding question asked in an interview, almost every problem requires you to demonstrate a deep understanding of data structures and algorithms. 

This course is a detailed review of some of the most common data structures and algorithms that you’ll see in interviews and your everyday work. With implementation details, thorough explanations, and hands-on coding exercises, you’ll quickly gain the confidence you need to solve any problem, no matter the situation.

Data Structures and Algorithms in Python

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.  

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. We assume the last element to be the *front* of the queue and the first element to be the *back* of the queue.   

To perform the enqueue operation, in the `enqueue` method, we make use of the `insert` method of Python list which will insert `item` on the `0`th index in `self.items` as specified on **line 6**. On the other hand, in the `dequeue` method, we use the `pop` method of Python list to pop out the last element as the queue follows the *First-In, First-Out* property. The method also ensures that the `pop` method is only called if the queue is not empty. To see if a queue is empty or not, the `is_empty` method comes in handy which checks for the length of `self.items` and compares it with `0`. If the length of `self.items` is `0`, `True` is returned, otherwise, `False` is returned.

The `peek` method will return the value of the last element in `self.items` which we assume to be the front of our queue. We have also overridden the `len` method on **line 19** which calls the `size` method on **line 22**. The size method returns the length of `self.items`. 

Now that we have successfully implemented the `Queue` class, let's go ahead and implement level-order traversal:

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

Introduction

Stack

Singly Linked Lists

Circular Linked Lists

Doubly Linked Lists

Arrays

Binary Trees

Binary Search Trees

Binary Search

Recursion

String Processing

Level-Order Traversal

Algorithm

Implementation