Inorder Traversal of a Tree in Python

1. Inorder Traversal of a Tree
2. Inorder Tree Traversal Implementation in Python

A Tree is a hierarchical data structure that consists of nodes connected by edges. Traversing a tree means visiting every node of the tree exactly once.

We traverse the tree for different purposes like displaying the nodes, finding the largest and smallest node, searching, sorting, etc. In this article, we will learn and implement the inorder traversal of a tree in Python.

Inorder Traversal of a Tree

Inorder traversal is a kind of depth-first traversal. Suppose we have the following tree.

If we apply inorder traversal, we will follow the steps below for each node.

1. First, we should visit all the nodes of the left subtree.
2. Then, we visit the parent node.
3. Then, we visit all the nodes in the right subtree.

We will get the nodes in the order 4, 2, 5, 1, 6, 3, 7.

Inorder Tree Traversal Implementation in Python

There are two ways to implement the inorder traversal in Python. The recursive and the iterative approach.

Recursive Approach

The recursive approach is easy to implement and understand. In the following code, we have created a class Node as a data structure to store the tree.

Each node consists of a value, its left and right child. The inorder traversal will recursively work for the left and right subtrees.

For every node, the inorder traversal will be performed by visiting its left node, the parent, and the right node.

Example Code:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.val))
        inorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Output:

Inorder traversal of the Tree
4
2
5
1
6
3
7

Iterative Approach

In an iterative approach, we must maintain a stack to store the nodes we will visit later. We created the class Node in the following code, just like before.

We have created an empty stack and started from the root node by making it the current node. If the current node exists, we will push it to the stack and go to its left node.

Else, if the node does not exist, we will pop an element from the stack and print it. When no left node exists, we will go to the right node by making it the current node.

We will repeat the same procedure iteratively until both the stack and the current element is empty.

Example Code:

from collections import deque


class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value


def inorder(root):
    stack = deque()
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            print(curr.val)
            curr = curr.right


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

Output:

Inorder traversal of the Tree
4
2
5
1
6
3
7