The Self-Taught Computer Scientist

1
2
3
4
5
6
8
7
Postorder: 4, 2, 7, 8, 5, 6, 3, 1
Figure 14.14: A postorder tree traversal

---

Data Structures
160
An in- order traversal is like a preorder and postorder traversal, but you print the node’s value (or 
do something else) in between your two recursive calls. When you use an in- order traversal, you move 
through a tree from the left to the root to the right, as shown in Figure 14.15.
Invert a Binary Tree
Max Howell is the creator of Homebrew, a popular package manager. He famously interviewed at 
Google for a position as a software engineer and was rejected. After the interview, he tweeted, “Google: 
90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a 
whiteboard, so ##$$ off.” Inverting a binary tree means swapping all the nodes in it. In other words, 
every right node becomes a left node, and every left node becomes a right node. In this section, you 
will learn how to invert a binary tree, so you don’t end up like Max Howell in a technical interview.
To invert a binary tree, you need to visit every node on it and keep track of each node’s children so 
that you can swap them. One way to accomplish this is using a breadth- first search, which allows you 
to easily keep track of each left and right child and switch them.
Here is the code to invert a binary tree:
class BinaryTree:
def __init__(self, value):
self.key = value
self.left_child = None
1
2
3
4
5
6
8
7
Inorder: 4, 2, 1, 7, 5, 8, 3, 6
Figure 14.15: An in- order tree traversal

---