The Self-Taught Computer Scientist

Data Structures
158
Here is the code for a preorder tree traversal:
def preorder(tree):
if tree:
print(tree.key)
preorder(tree.left_child)
preorder(tree.right_child)
Your function recursively calls itself until it hits its base case, which is this line of code:
if tree:
This line of code prints each tree node’s value:
print(tree.key)
And these lines of code call 
preorder
on each tree node’s left child and right child:
preorder(tree.left_child)
preorder(tree.right_child)
This traversal should be familiar to you because it is similar to what you did when you wrote merge 
sort in Chapter 4. When you coded the merge sort, you put a recursive call to the left half of a list 
followed by a recursive call to the right half of a list. Your algorithm called itself with the left half until 
you had a list with only one item. Your algorithm called your recursive code to break up your right 
1
2
3
4
5
6
8
7
 Preorder: 1, 2, 4, 3, 5, 7, 8, 6
Figure 14.13: A book represented as a tree

---

Chapter 14 Binary Trees
159
half of the list whenever that happened. When you hit your base case, you moved up a level in your 
recursive stack and merged the two lists with the code you wrote underneath your two recursive calls. 
Your merge sort algorithm is similar to a preorder traversal but is called a 
postorder traversal. The 
difference between a postorder traversal and a preorder traversal is that you print each node’s value 
(or do something else) after your recursive calls in a postorder traversal.
def postorder(tree):
if tree:
postorder(tree.left_child)
postorder(tree.right_child)
print(tree.key)
With a postorder traversal, you move through a tree starting on the left, then moving to the right, 
and ending with the root, as shown in Figure 14.14.
If you imagine a postorder traversal as your merge sort algorithm, you print a node every time you 
make a merge.
Finally, you have an in- order traversal.
def inorder(tree):
if tree:
inorder (tree.left_child)
print(tree.key)
inorder (tree.right_child)