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

Pre-order traversal and prefix notation

Pre-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. The pre-order tree traversal works as follows:

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

So, to traverse a tree in pre-order mode, we visit the tree in the order of root node, the left sub-tree, and the right sub-tree node.

Consider the following example tree to understand pre-order traversal:

In the preceding example of a binary tree, first, we visit root ...