Perform BFS on a Binary Tree

Question

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


    def Breadth_first_search(self,root):
        """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 "
t.Breadth_first_search(t.root)

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

Answer 1

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)

5. 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().

6. 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