Implement Inorder Tree Traversal - Python

The inorder traversal is a systematic way of visiting all nodes in a binary tree. This mode of traversal is unique to binary trees and cannot be applied to other type of trees.

A binary tree is a type of tree where each node has at most two children. The children are usually referred to as, left child and right child of the node.

The following figure shows an example of a binary tree:

In inorder traversal algorithm, the nodes in a binary tree are visited recursively in the following order:

This means that the left subtree of each node is visited first, followed by the root node, and then the right subtree. 

In the tree shown in the above figure, inorder traversal would visit the nodes in the following order:

As you can see from the above sequence, inorder traversal mode always begins at the leftmost node and ends at the rightmost.

inorder traversal Algorithm

The inorder traversal can be implemented recursively based on the following algorithm:

The recursive nature of the algorithm makes it possible to perform inorder traversal on a subtree rooted at a given node instead of just for the entire tree.

Inorder traversal implementation

In this section we will implement the inorder() function for performing inorder traversal an on a subtree rooted at the node given as argument.

def inorder(n):
    if n.left:
        inorder(n.left)
    print(n.val)
    if n.right:
        inorder(n.right)

The above function will work with any binary tree whose nodes defines left and right attributes to represent the left and the right child respectively.

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

root = Node(4)
n1 = Node(3)
n2 = Node(13)
n3 = Node(2)
n4 = Node(1)
n5 = Node(6)
n6 = Node(14)

root.left = n1
root.right = n2
n1.left = n3
n1.right = n4
n2.left = n5
n2.right = n6

inorder(root) #implementation of the inorder() function is omitted, refer to the previous section 

The binarytree module

The binarytree library provides an implementation of a Node class that has more features than the one we just implemented above. To install the library, run the following pip commad:

pip install binarytree

The tree function in the binarytree module creates a binary tree that is pre-filled with random values. The function takes in the length of the tree to be generated as argument.

from binarytree import tree

#the inorder() function
def inorder(n):
    if n.left:
        inorder(n.left)
    print(n.val)
    if n.right:
        inorder(n.right)

T = tree(3) #create a tree of length 3 pre-filled with random integers
print(T)

#use the inorder function 
print('inorder:')
inorder(T)