Hands-On Data Structures and Algorithms with Python - Second Edition

In-order traversal and infix notation

In-order tree traversal works as follows. First of all, we check if the current node is null or empty. If it is not empty, we traverse the tree. In in-order tree traversal, we follow these steps:

1. We start traversing the left sub-tree and call the inorder function recursively
2. Next, we visit the root node
3. Finally, we traverse the right sub-tree and call the inorder function recursively

So, in a nutshell, in in-order tree traversal, we visit the nodes in the tree in the order of (left sub-tree, root, right sub-tree).

Let's consider an example to understand in-order tree traversal:

In the example binary ...