Tree Traversal Algorithms in Python

Ashish Katri

a year ago

Tree Traversal Algorithms In Python
Tree Traversal Algorithms In Python
“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

Inorder 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 Inorder 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.

Submit Review

We're Online!

Chat now for any query