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’.
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:
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:
or for any other doubts, you can send a mail to me also.
Hello, my name is Prashant, and I'm currently pursuing my Bachelor of Technology (B.Tech) degree. I'm in my 3rd year of study, specializing in machine learning, and attending VIT University.
In addition to my academic pursuits, I enjoy traveling, blogging, and sports. I'm also a member of the sports club. I'm constantly looking for opportunities to learn and grow both inside and outside the classroom, and I'm excited about the possibilities that my B.Tech degree can offer me in terms of future career prospects.
Thank you for taking the time to get to know me, and I look forward to engaging with you further!
