0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ The question and answer are about breath-first traversal, not breadth-first search. \$\endgroup\$ – raindrop Dec 3 '18 at 3:03
5
\$\begingroup\$
  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
    
\$\endgroup\$
  • \$\begingroup\$ I read this whole thing to the bottom just to see if we caught that OP was never searching in the first place :/ \$\endgroup\$ – T.Woody Nov 13 '18 at 4:16
  • 1
    \$\begingroup\$ @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 . \$\endgroup\$ – mu 無 Nov 13 '18 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.