The Self-Taught Computer Scientist

Chapter 14 Binary Trees
161
self.right_child = None
def insert_left(self, value):
if self.left_child == None:
self.left_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.left_child = self.left_child
self.left_child = bin_tree
def insert_right(self, value):
if self.right_child == None:
self.right_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.right_child = self.right_child
self.right_child = bin_tree
def invert(self):
current = [self]
next = []
while current:
for node in current:
if node.left_child:
next.append(node.left_child)
if node.right_child:
next.append(node.right_child)
tmp = node.left_child
node.left_child = node.right_child
node.right_child = tmp
current = next
next = []
The code is the same as your breadth- first traversal to search for a number, but instead of checking 
whether a node’s value is 
n
, you swap the right and left child each iteration.
To accomplish this, you have to first save 
node.left_child
in a temporary variable called 
tmp
. 
Then, you set 
node.left_child
to 
node.right_child
and 
node.right_child
to 
tmp
, which swaps 
the two child nodes.
tmp = node.left_child
node.left_child = node.right_child
node.right_child = tmp
When your algorithm finishes, you have successfully inverted your binary tree.
Another, more elegant way to invert a binary tree is to use a depth- first traversal, which you can 
try in the challenges.

---

Data Structures
162
Vocabulary
tree: A nonlinear abstract data type made up of nodes connected in a hierarchical structure.