Traverse Trees Using Level Order Traversal in Python

Prashant Sharma 30 Nov, 2021 • 5 min read

This article was published as a part of the Data Science Blogathon

Overview

Trees are a non-linear data structure type. The trees are composed of nodes grouped in a hierarchical fashion. It begins with a single root node that may have child nodes of its own. All nodes are linked by edges. We can use trees to store information in a hierarchical fashion. Trees are grouped into many forms based on the number of children at each node. We will do Level Order Traversal in Python for trees in this tutorial.

What is traversal?

Traversing is the process of traveling a tree node by node, level by level until all nodes have been searched. The term “level order traversal” relates to the method for traversing breadth-first binary trees. Binary trees are trees with a maximum of two child nodes per node.

The traversal starts at the root node. Then we go to the root node’s child nodes, followed by their child nodes, and so on until all leaf nodes have been explored. We explore a tree using breadth-first traversal, starting at the root node and progressively moving towards its neighbors. Before proceeding to the next level, we verify that all nodes for that depth are still present.

Let us illustrate the traversal using the following tree

Node ‘0’ is the root node in this case, whereas nodes ‘1’ and ‘2’ are its child nodes. The left child node is node ‘1,’ while the right child node is node ‘2.’ Due to the binary nature of the tree, each node may have a maximum of two child nodes. Nodes ‘3’ and ‘4’ are thus child nodes of node ‘1’. Nodes ‘5’ and ‘6’ are subordinate nodes of node ‘2’.

illustrate the traversal using the following tree

If we were to traverse the above tree in level order, it would be as follows:

0 1 2 3 4 5 6 

We would begin by traversing node ‘0’, followed by its sibling nodes – node ‘1’ and node ‘2’. Following that, we would explore node ‘1″s child nodes – node ‘3’ and node ‘4’. Finally, we would explore node ‘2″s child nodes — node ‘5’ and node ‘6’. After all, nodes have been explored, the traversal will come to a halt.

Python Level Order Traversal Implementation

We will use queues to implement level order traversal in Python. The queue is a data structure that is linear in nature. We store things in a queue according to the FIFO principle — First In, First Out. That is, the first piece placed into the queue will also be the first thing pulled from it. We’re going to use a list to construct a queue.

To begin, we will insert the root node into the queue. After visiting the root nodes, we will pop out the root node and insert its child nodes into the queue.

We will explore each child node and determine whether it is a root node for any additional nodes. This process will be repeated until no more child nodes are added to the queue and the queue becomes empty.

Implementation of Python Code for Level Order Traversal

As discussed before, we will use a queue to conduct level order traversal. We will traverse the following tree:

Implementation of Python Code for Level Order Traversal

The root node, in this case, is ‘A’. It has two child nodes: node ‘B’ is on the left, and node ‘C’ is on the right. Node ‘B’ contains two child nodes: ‘D’ and ‘E.’ Whereas node ‘C’ has a single child, node ‘F.’

Defining the class

To begin, we’ll create a class called ‘Tree’.

class Tree:
  def __init__(self,node):
    self.node = node
    self.left = None
    self.right = None

We’ll construct the __init__() function, which takes two parameters: self and node. We’ve set self.node to node. Self.left and self.right will initially be None. self.left and self.right denote the root node’s( self.node ) left and right child nodes, respectively. self.node.

Creating the function for traversal

Then, we’ll create a function called ‘Level_Order_Traversal’ outside the class.

def Level_Order_Traversal(root):
  traversed = []
  traversed.append(root)
  if root is None:
    return traversed
  while traversed != []:
    print(traversed[0].node)
    x = traversed.pop(0) 
    if x.left:
      traversed.append(x.left)
    if x.right:
      traversed.append(x.right)

The function takes a single parameter, ‘root,’ which refers to the root node. A list labeled ‘traversed’ serves as a queue. To begin, we’ll add the root to the list, which is really a class object. Then, we’ll determine whether or not our root directory is empty. If the queue is empty, we will return the empty queue as ‘traversed’.

Following that, we’ll execute a while loop until the traversed list is empty. We’ll use ‘print(traversed[0].node)’ to output the root node.

It will print the value of the list’s first entry. Following that, we’ll remove the printed element from the list and store it to the variable ‘x’. Then, we’ll check to see whether the node that was popped from the ‘traversed’ queue has any remaining child nodes.

If it has, we will add the left child node to the ‘traversed’ collection. Similarly, we will look for the appropriate child node.

The process of creating class objects

To begin, we’ll generate the root ‘A’. Then, we’ll construct the full tree using the left and right properties. Following that, we’ll invoke the Level_Order_Traversal() function, handing it root as an argument.

root = Tree('A')
root.left = Tree('B')
root.right = Tree('C')
root.left.left = Tree('D')
root.left.right = Tree('E')
root.right.left = Tree('F')
Level_Order_Traversal(root)

The following is the result of the left order traversal:

A
B
C
D
E
F

The entire program is:

class Tree:
  def __init__(self,node):
    self.node = node
    self.left = None
    self.right = None
def Level_Order_Traversal(root):
  traversed = []
  traversed.append(root)
  if root is None:
    return traversed
  while traversed != []:
    print(traversed[0].node)
    x = traversed.pop(0) 
    if x.left:
      traversed.append(x.left)
    if x.right:
      traversed.append(x.right)
root = Tree('A')
root.left = Tree('B')
root.right = Tree('C')
root.left.left = Tree('D')
root.left.right = Tree('E')
root.right.left = Tree('F')
Level_Order_Traversal(root)

Execution of the code

The first root node displayed in this case would be ‘A’, which was popped from ‘traversed’. Then we’d determine if ‘A’ has any child nodes. As a result, the words ‘B’ and ‘C’ would be attached to ‘traversed’. The ‘queue traversed’ would be as follows:

Traversed :   | A | B | C |    |    |    |

Then we would print and remove the node ‘B’ from the queue. Following that, we would determine if node ‘B’ has any left or right child nodes. Due to the fact that it contains child nodes, ‘D’ and ‘E’ would be attached to ‘traversed’.

Traversed :   | A | B | C | D | E |    |  

Following that, we’ll print and remove node ‘C’ from the queue. Then, we’ll determine if it has any child nodes. Given that it has one left child node – ‘F’ – we would add ‘traversed’ to it.

Traversed :   | A | B | C | D | E | F |   

We’re now going to print ‘D’ and remove it from the queue. We will not add anything to the queue since ‘D’ has no child nodes. Likewise, we will print ‘E’ and ‘F’ sequentially and remove them from the queue.

Traversed :   | A | B | C | D | E | F |   

Because the queue ‘traversed’ is now empty, the while loop will terminate.

Hope you like the article. If you want to connect with me then you can connect on:

Linkedin

or for any other doubts, you can send a mail to me also.

The media shown in this article are not owned by Analytics Vidhya and are used at the Author’s discretion.
Prashant Sharma 30 Nov 2021

Currently, I Am pursuing my Bachelors of Technology( B.Tech) from Vellore Institute of Technology. I am very enthusiastic about programming and its real applications including software development, machine learning and data science.

Frequently Asked Questions

Lorem ipsum dolor sit amet, consectetur adipiscing elit,

Responses From Readers

Clear

Machine Learning
Become a full stack data scientist