I need help traversing a BFS. I think I followed the instructions correctly but

Question

 I need help traversing a BFS. I think I followed the instructions correctly but I continue to get an error. The error that im getting is " node = Q.pop(0) IndexError: pop from empty list" I need to pass the test below. Can someone explain to me why it is saying that I am popping from an empty list. I thought node = Q.pop(0) was popping my list and setting it equal to node. I need to return a list. 

 # create a Q with the root element, and an empty list # while there are nodes in the Q # grab the first one and add it to the result list # if there is a node to the left, add that to the Q # if there is a node to the right, add that to the Q

 def test_BFS(self):     bt = binary_search_tree([20, 10, 30, 25, 35])     self.assertEqual(bt.BFS(), [20, 10, 30, 25, 35]) 

 class binary_search_tree:     def __init__(self, init=None):         self.__value = self.__left = self.__right = None          if init:             for i in init:                 self.add(i)      def __iter__(self):         if self.__left:             for node in self.__left:                 yield (node)          yield (self.__value)          if self.__right:             for node in self.__right:                 yield (node)      def __str__(self):         return (','.join(str(node) for node in self)) 

 def BFS(self):     if self.__value is None:         return [None]     else:         Q = [self]         resultlist = []         while Q is not None:             node = Q.pop(0)             if node.__left is not None:                 resultlist.append(self.__left)             if node.__right is not None:                 resultlist.append(self.__right)     return resultlist

Explanation / Answer

IN your code, Q is an list and you are putting Q=[self]

Above statement means, Q will always point to a list, but that list may or may not have any elements present inside it.

So Q will never be equal to None, as it always points towards Q.

The correct condition to be check will be while len(Q) != 0:

It checks while list is having more than one element, you keep on popping. You get the error on pop statement, because list might not contain any element. If you change the while loop condition like i said yesterday, you will never encounter a case, where you pop from empty list. Let me know if more help is needed. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.