Download our e-book of Introduction To Python
Related Blog
Discuss Microsoft Cognitive ToolkitMatplotlib - Subplot2grid() FunctionMicrosoft Cognitive Toolkit (CNTK) - CPU and GPUMatplotlib - PyLab moduleMatplotlib - Twin AxesMatplotlib - MultiplotsMatplotlib - Working with ImagesMatplotlib - Working With TextPython Forensics - Memory and ForensicsMatplotlib - Setting Ticks and Tick Labels View More
Top Discussion
How can I write Python code to change a date string from "mm/dd/yy hh: mm" format to "YYYY-MM-DD HH: mm" format? Exception Type: JSONDecodeError at /update/ Exception Value: Expecting value: line 1 column 1 (char 0) Someone guide please. How to store the name of IV in a list which show non linear behavior ?.......How to understand data is linear or non linear ? 'collections.OrderedDict' object has no attribute 'status_code' What is the difference between a module and a package in Python? How can i use pyspark to parallelize a file's payload How to leave/exit/deactivate a Python virtualenvironment Join Discussion
Top Courses
Webinars
Generative AI Journey in Data Science
Dec 6th (8:00 PM) 1982 Registered
Tree Traversal Algorithms in Python
Ashish Katri
2 years ago
Table of Content
- Traversal is a process
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
“In computer science, tree traversal (also known as tree search)
is a form of graph traversal and refers to the process of visiting (checking
and/or updating) each node in a tree data structure, exactly once. Such
traversals are classified by the order in which the nodes are visited.” —
Wikipedia
So,
in short Traversal is a process to visit all the nodes of a tree and may print
their values too. Because all nodes are connected via edges (links) we always
start from the root (head) node. That is, we cannot randomly access a node in a
tree.
Traversal
can be performed in three ways −
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
In-order Traversal
In order Traversal is the one the most used variant of
DFS(Depth First Search) Traversal of the tree.
As DFS suggests, we will first focus on the depth of the
chosen Node and then go to the breadth at that level. Therefore, we will start
from the root node of the tree and go
deeper-and-deeper into the left subtree with a recursive manner.
When we will reach to the left-most node with the above
steps, then we will visit that current node and go to the left-most node of its
right subtree (if exists).
The same steps should be followed in a recursive manner to
complete the inorder traversal. The order of those steps will be like (in recursive
function).
1.
Go to left-subtree
2.
Visit Node
3.
Go to right-subtree
Let’s understand with the example
In
this traversal method, the left subtree is visited first, then the root and
later the right sub-tree. We should always remember that every node may
represent a subtree itself.
In the python program, we use the Node class to create place holders for the
root node as well as the left and right nodes. Then we create an insert function
to add data to the tree. Finally, the Inorder traversal logic is implemented by
creating an empty list and adding the left node first followed by the root or
parent node. At last, the left node is added to complete the Inorder traversal.
Please note that this process is repeated for each sub-tree until all the nodes
are traversed.
class Node:
def __init__(self, data):
self.left = none
self.right = none
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is none:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is none:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))
When
the above code is executed, it produces the following result −
[10, 14, 19, 27, 31, 35, 42]
Pre-order Traversal
Preorder Traversal is another variant of DFS. Where
atomic operations in a recursive function, are as same as In order traversal but
with a different order.
Here, we visit the current node first and then go to
the left sub-tree. After covering every node of the left sub-tree, we will move
towards the right sub-tree and visit in a similar fashion.
Order of the steps will be like…
1.
Visit Node
2.
Go to left-subtree
3.
Go to right-subtree
Let’s understand with an example
In
this traversal method, the root node is visited first, then the left subtree
and finally the right subtree.
In the python program, we use the Node class to create place holders for the
root node as well as the left and right nodes. Then we create an insert function
to add data to the tree. Finally, the Pre-order traversal logic is implemented
by creating an empty list and adding the root node first followed by the left
node. At last, the right node is added to complete the Pre-order traversal.
Please note that this process is repeated for each sub-tree until all the nodes
are traversed.
class Node:
def __init__(self, data):
self.left = none
self.right = none
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is none:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is none:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))
When
the above code is executed, it produces the following result −
[27, 14, 10, 19, 35, 31, 42]
Post-order Traversal
Similar goes with Postorder Traversal. Where we visit
the left subtree and the right subtree before visiting the current node in
recursion.
So, the sequence of the steps will be…
1.
Go to left-subtree
2.
Go to right-subtree
3.
Visit Node
Let’s understand with an example
In this traversal method, the root node is visited last, hence
the name. First, we traverse the left subtree, then the right subtree and
finally the root node.
In the python program, we use the Node class to create place holders for the
root node as well as the left and right nodes. Then we create an insert function
to add data to the tree. Finally, the Post-order traversal logic is implemented
by creating an empty list and adding the left node first followed by the right
node. At last, the root or parent node is added to complete the Post-order
traversal. Please note that this process is repeated for each sub-tree until
all the nodes are traversed.
class Node:
def __init__(self, data):
self.left = none
self.right = none
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is none:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is none:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))
When
the above code is executed, it produces the following result −
[10, 19, 14, 31, 42, 35, 27]
Learn more about the transverse algorithms in Python InsideAIML.
Or if you are into videos, then we have an amazing Youtube channel as well. Visit our InsideAIML Youtube Page to learn all about Artificial Intelligence, Deep Learning, Data Science and Machine Learning.
Keep Learning. Keep Growing