The Self-Taught Computer Scientist

Data Structures
154
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.right_child
bin_tree.left_child = bin_tree 
First, your method checks to see whether 
self.left_child
is 
None
. If it is, you create a new 
BinaryTree
class and assign it to 
self.left_child
.
if self.left_child = None:
self.left_child = BinaryTree(value)
Otherwise, you create a new 
BinaryTree
object, assign whatever 
BinaryTree
object is currently at 
self.left_child
to the new 
BinaryTree
’s 
self.left_child
, and then assign the new 
BinaryTree
to 
self.left_child
.
else:
bin_tree = BinaryTree(value)
bin_tree.left_child = self.left_child
self.left_child = bin_tree
After defining the 
insert_left
method, you also define a method called 
insert_right
, which does 
the same thing as 
insert_left
but adds a new node to the right side of your binary tree instead.
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
Now you can create a binary tree and add nodes to it like this:
tree = BinaryTree(1)
tree.insert_left(2)
tree.insert_right(3)
tree.insert_left(4)
tree.left_child.insert_right(6)
tree.insert_right(5)

---

Chapter 14 Binary Trees
155
This code creates the binary tree in Figure 14.11.
Breadth- First Tree Traversal
As you learned earlier, you cannot always traverse a tree by moving from node to node without back-
tracking. That doesn’t mean you cannot search a tree for data, though. To search a tree for a piece of 
data, you need to visit every node in your tree and see if it contains the information you are looking 
for. There are several ways to visit each node in a binary tree. One way is a breadth- first traversal: a 
method of visiting every node in a tree by visiting each node in it level by level. For example, in the 
binary tree in Figure 14.12, the root is level 0, followed by levels 1, 2, and 3.
When you use a breadth- first traversal to perform a search, you call it a breadth- first search. You 
start a breadth- first search at the root of your tree (level 0) and go level by level through your tree, 
visiting each node one by one on each level until you reach the final level. You can code a breadth- first 
search by using two lists to track your tree’s current and next level. As you visit each node in your 
current list, you check to see if it matches the data you are looking for and add its children to your 
“next” list. When it is time to move to the next level, you switch the lists. Here is how to look for a 
number in a binary tree using a breadth- first search:
1
4
6
2
5
3
Figure 14.11: A binary tree with five nodes
2
Level 0
Level 1
Level 2
Level 3
5
9
2
6
9
4
11
6