Trying to implement simple BFS in python...Not able to print the value if search is successful

Question

Below code is a simple implementation of BFS in Python. I able to print the values level by level from a tree. However when I want to search a element and print it . I am not able to do it. Whts is the error?

    def search_bfs(self,root,key):
        q=QueueClass()
        q.enqueue(root)
        while q.size() > 0:
            curr_node = q.dequeue()
            #print curr_node
            #print key
            if curr_node == key:
                print curr_node
                break
            if curr_node.left is not None:
                q.enqueue(curr_node.left)
            if curr_node.right is not None:
                q.enqueue(curr_node.right)
from QueueClass import QueueClass
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None

    def __str__(self):
        return str(self.data)

class searchtree:
    def __init__(self):
        self.root = None

    def create(self,val):
        if self.root == None:
            self.root=Node(val)
        else:
            current=self.root
            while 1:
                if val < current.data:
                    if current.left:
                        current=current.left
                    else:
                        current.left=Node(val)
                        break
                if val > current.data:
                    if current.right:
                        current=current.right
                    else:
                        current.right=Node(val)
                        break
                else:
                    break
tree=searchtree()
lst=[3,1,2,6,4,5,8,12]
for i in lst:
    tree.create(i)
tree.search_bfs(tree.root, 3)

Can you tell us what is the error? Is it just that nothing is printed? Is the curr_node == key line definitely being reached? How do you know? — Tom Dalton
– Tom Dalton, Commented Feb 1, 2015 at 1:44
Yeah nothing is printed. the statment inside curr_node == key is not being reached, even when I pass a key element matching to root. However printing curr_node prints all the members. — mrsan22
– mrsan22, Commented Feb 1, 2015 at 1:46
Can you tell us a bit more about the elements? What kind of objects are they? — VHarisop
– VHarisop, Commented Feb 1, 2015 at 1:53
As @VHarisop implies, the problem is likely with your values - can you provide the full code for what you're passing into search_bfs()? — Tom Dalton
– Tom Dalton, Commented Feb 1, 2015 at 1:54
Got it. I just checked its type and its of type of 'object'. I need to used curr_node.data in the if statement. Let me know if I have understood it. — mrsan22
– mrsan22, Commented Feb 1, 2015 at 2:02

Alex Martelli · Accepted Answer · 2015-02-01 02:07:06Z

2

You really make it hard to reproduce your problem! So here's what I did:

class QueueClass(object):
    def __init__(self):
        self.l = []
    def size(self): return len(self.l)
    def enqueue(self, it): self.l.append(it)
    def dequeue(self): return self.l.pop()

class Node:
    def __init__(self, name, left=None, right=None):
        self.name = name
    self.left = left
    self.right = right
    def __str__(self):
        return '{}:{}/{}'.format(self.name, self.left, self.right)

root = Node('root')

adding all the code you omitted (more than you supplied!-).

And now, adding your code exactly as reported, the call:

search_bfs(None, root, root)

emits

root:None/None

exactly as desired and contrary to your report.

It follows that your bug is in some of code you didn't show us, not in the coded you did show.

You either have a buggy queue-class, or are building a different tree than you thought, or searching for a node that is not actually in the tree.

Hard to debug code you're now showing, you know.

Added: so now I've integrated the extra code per your edit and at the end I have:

st = searchtree()
st.create('imtheroot')
st.search_bfs(st.root, st.root)

and of course it prints imtheroot as expected.

Is your bug perhaps STILL hiding in parts you're not yet showing, e.g instead of looking for a node you may be looking for something else?

E.g, if the final call was erroneously st.search_bfs(st.root, 'imtheroot') then obviously the search would fail -- you're checking equality of the key parameter with a node, so key clearly must be a node. not a string or other things (unless the Node class defines a very, very peculiar __eq__ method, which the one you've shown fortunately doesn't:-).

edited Feb 1, 2015 at 2:07

answered Feb 1, 2015 at 1:59

Alex Martelli

887k175 gold badges1.3k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mrsan22 Over a year ago

Thanks Alex. I was comparing a key to a node. I hv fixed it now.

Alex Martelli Over a year ago

@user1743585, so pls accept an answer, either my very long one or Tom's concise one, so this issue can be closed.

Tom Dalton · Accepted Answer · 2015-02-01 02:07:15Z

1

I think the issue is that when you do if curr_node == key, curr_node is a Node object, which has an integer .data attribute, but key is the integer value.

So I think you just need to use if curr_node.data == key.

answered Feb 1, 2015 at 2:07

Tom Dalton

6,19027 silver badges36 bronze badges

1 Comment

mrsan22 Over a year ago

Thanks for your help Tom. I was doing the same mistake. Comparing a Node type to a integer.

Collectives™ on Stack Overflow

Trying to implement simple BFS in python...Not able to print the value if search is successful

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related