Breadth First Search (BFS) Python Implementation...where is the bug here?

Question

I have written the code below to implement breadth-first search using python. I'm not sure how the .children property is working and .val does not. I've added some print statements to see what's happening but I'm still not sure. The error I get when I run the code is:

Traceback (most recent call last): File "bfs.py", line 31, in bfs(Node1) File "bfs.py", line 24, in bfs print popped.children[0].val AttributeError: 'tuple' object has no attribute 'val'

Here is the code...any help will be very much appreciated.

class Node:
    def __init__(self, children, val):
        self.children = children
        self.val = val

Node8 = ([], 8)
Node7 = ([], 7)
Node6 = ([], 6)
Node5 = ([Node6], 5)
Node4 = ([], 4)
Node3 = ([Node7], 3)
Node2 = ([Node4, Node5], 2)
Node1 = Node([Node2, Node3, Node8], 1)


def bfs(r):
    node_list = [r]
    while len(node_list) > 0:
        popped = node_list.pop(0)
        print popped.val
        print "debug"
        print popped.children
        print popped.children[0]
        print popped.children[0].val
        for child in popped.children:
            print child.val
            node_list.append(child)
            print "appended"


bfs(Node1)

Answer 1

You aren't calling the Node constructor that you created when you create any Node other than Node1. You are instead creating 2-tuples, which have no val attribute. Add a call to your Node constructor and everything should work fine:

# ...
Node8 = Node([], 8)
Node7 = Node([], 7)
Node6 = Node([], 6)
Node5 = Node([Node6], 5)
Node4 = Node([], 4)
Node3 = Node([Node7], 3)
Node2 = Node([Node4, Node5], 2)
Node1 = Node([Node2, Node3, Node8], 1)
# ...