Python Data Structures and Algorithms

In-order traversal and infix notation

Most of us are probably used to this way of representing an arithmetic expression, since this is the way we are normally taught in schools. The operator is inserted (infixed) between the operands, as in 3 + 4. When necessary, parentheses can be used to build a more complex expression: (4 + 5) * (5 - 3).

In this mode of traversal, you would visit the left sub-tree, the parent node, and finally the right sub-tree.

The recursive function to return an in-order listing of nodes in a tree is as follows:

    def inorder(self, root_node):         current = root_node         if current is None:             return         self.inorder(current.left_child)         print(current.data)         self.inorder(current.right_child) 

We visit the node by printing the node ...