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:

**Left child** → **Root** → **Right child**

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:

0, 2, 10, 3, 9, 1, 7, 4, 8, 6, 13, 14

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:

function inorder(n):

if n has a left child 'left' then:

inorder(left)

process n

if n has a right child 'right' then:

inorder(right)

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
```

inorder:

2

3

1

4

6

13

14

## 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)
```