Python Data Structures and Algorithms

Pre-order traversal and prefix notation

Prefix notation is commonly referred to as Polish notation. Here, the operator comes before its operands, as in + 3 4. Since there is no ambiguity of precedence, parentheses are not required: * + 4 5 - 5 3.

To traverse a tree in pre-order mode, you would visit the node, the left sub-tree, and the right sub-tree node, in that order.

Prefix notation is well known to LISP programmers.

The recursive function for this traversal is as follows:

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

Note the order in which the recursive call is made.