The Self-Taught Computer Scientist

Figure 14.12: Levels in a binary tree

---

Data Structures
156
class BinaryTree:
def __init__(self, value):
self.key = value
self.left_child = None
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 breadth_first_search(self, n):
current = [self]
next = []
while current:
for node in current:
if node.key == n:
return True
if node.left_child:
next.append(node.left_child)
if node.right_child:
next.append(node.right_child)
current = next
next = [] 
return False
Your method, 
breadth_first_search
, takes one parameter, 
n
, which is the data to search for:
def breadth_first_search(self, n):
Next, you define two lists. You use the first list, 
current
, to keep track of the nodes in the current level 
you are searching. You use the second list, 
next
, to keep track of the nodes in the next level. You also 
add 
self
to 
current
, so your algorithm starts by searching your tree’s root (level zero).
current = [self]
next = []

---

Chapter 14 Binary Trees
157
Your 
while
loop continues as long as 
current
still contains nodes to search.
while current:
Then you use a 
for
loop to iterate through every node in 
current
.
for node in current:
If the node’s value matches 
n
(the value you are searching for), you return 
True
.
if node.key == n:
return True
Otherwise, you append the node’s left and right child nodes to your 
next
list, if they’re not 
None
, so 
they get searched when you search the next level.
if node.left_child:
next.append(node.left_child)
if node.right_child:
next.append(node.right_child)
Then, at the end of your 
while
loop, you swap your lists 
current
and 
next
. The list of nodes to search 
next becomes the list of nodes to search now, and you set 
next
to an empty list.
current = next
next = []
If your 
while
loop terminates, you return 
False
because your breadth- first search did not find 
n
in the tree.
return False
More Tree Traversals
A breadth- first traversal is not the only way to traverse a binary tree: you can also do a depth- first 
traversal. In a depth- first traversal, you visit all the nodes in a binary tree by going as deep as you 
can in one direction before moving to the next sibling. Depth- first traversal offers three ways to visit 
every node: preorder, postorder, and in order. The implementations of the three approaches are sim-
ilar, but their uses are different.
Say you have a binary tree shown in Figure 14.13. In preorder traversal, you start with the root and 
move to the left and then to the right. 

---