Perform BFS on a Binary Tree

Task: Perform Breadth first traversal on a Binary Search Tree and print the elements traversed.

class Node(object):
def __init__(self, value,left=None, right=None):
self.value = value
self.left = left
self.right = right

class BinarySearchTree(object):
def __init__(self, value):
self.root = Node(value)

def insert(self, value):
current = self.root
while current:
if value > current.value:
if current.right is None:
current.right = Node(value)
break
else:
current = current.right
else:
if current.left is None:
current.left = Node(value)
break
else:
current = current.left

"""In BFS the Node Values at each level of the Tree are traversed before going to next level"""

visited = []
if root:
visited.append(root)
print root.value
current = root
while current :
if current.left:
print current.left.value
visited.append(current.left)
if current.right:
print current.right.value
visited.append(current.right)
visited.pop(0)
if not visited:
break
current = visited[0]

t = BinarySearchTree(100)
t.insert(12)
t.insert(92)
t.insert(112)
t.insert(123)
t.insert(2)
t.insert(11)
t.insert(52)
t.insert(3)
t.insert(66)
t.insert(10)

print "Output of Breadth First search is "


The code runs acceptably and gives the correct output. Is there better solution to this problem?

• The question and answer are about breath-first traversal, not breadth-first search. Dec 3, 2018 at 3:03

1. PEP-0008: your method names should follow snake_case style, and there should be a space between arguments. So change your method singature to:

def breadth_first_search(self, root):
# remaining code

2. You maintain a list called as visited, however the nodes added in it are ones which are yet to be visited. Call it to_visit instead. One should use the variable name visited to keep track of nodes that are visited already.

to_visit = []
if root:
to_visit.append(root)
print( root.value)
# remainig code with to_vist replacing visited

3. You assign the node at the end, and pop the current node just before that. Better to do this in the beginning of the loop, and iterate over the existence of elements within the list. This way, your code gets much concise and clean:

while to_visit:
current = to_visit.pop(0)
if current.left:
print( current.left.value)
to_visit.append(current.left)
if current.right:
print( current.right.value)
to_visit.append(current.right)

4. You pre-check and print the value of the left and right child, and that of root as well. It would be better if these statements could be reduced:

while to_visit:
current = to_visit.pop(0)
print( current.value)
if current.left:
to_visit.append(current.left)
if current.right:
to_visit.append(current.right)


So now, your function looks like

def breadth_first_search(self, root):
"""In BFS the Node Values at each level of the Tree are traversed before going to next level"""

to_visit = []
if root:
to_visit.append(root)
while to_visit:
current = to_visit.pop(0)
print( current.value)
if current.left:
to_visit.append(current.left)
if current.right:
to_visit.append(current.right)

1. But this gets called as t.Breadth_first_search(t.root), since root is already present, we can use a default value here. Also, the list can be initialized with an element, so we save the append call:

def breadth_first_search(self, root=None):
"""In BFS the Node Values at each level of the Tree are traversed before going to next level"""

root = self.root if root is None else root
to_visit = [root]
while to_visit:
current = to_visit.pop(0)
print(current.value)
if current.left:
to_visit.append(current.left)
if current.right:
to_visit.append(current.right)


And now, you can call it as t.breadth_first_search().

2. But wait, if it is breadth_first_search, shouldn't you be searching for something? Well no, your question states to do a breadth first traversal, so you should rename your method to:

def breadth_first_traversal(self, root=None):
# remaining code as above

• I read this whole thing to the bottom just to see if we caught that OP was never searching in the first place :/ Nov 13, 2018 at 4:16
• @T.Woody I guess I flipped it the other way in point 6; my hunch was that OP is supposed to do a traversal and so should rename the method to breadth_first_traversal instead of breadth_first_search . Nov 13, 2018 at 4:33