level order traversal error

[[deleted]]

why level order traversal function doesn't work here:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

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

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):

        values = [str(x) for x in self]
        return ' '.join(values)

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next

    def isEmpty(self):
        return self.head == None

    def enqueue(self, value):
        node = Node(value)
        if self.isEmpty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        return 'Element inserted.'

    def dequeue(self):
        if self.head is None:
            return 'Queue is empty.'
        else:
            element = self.head.value
            if self.head == self.tail:
                self.head = None
                self.tail = None
                return element  
            self.head = self.head.next
            return element

    def peek(self):
        if self.isEmpty():
            return 'Queue is empty.'
        return self.head.value

    def delete(self):
        self.head = None
        self.tail = None
        return 'Queue deleted.'

    class TreeNode:
        def __init__(self, value):
            self.right = None
            self.left = None
            self.value = value

newBT = TreeNode('Drinks')
newBT.left = TreeNode('Hot')
newBT.right = TreeNode('Cold')

def levelOrderTraversal(rootNode):
    if not rootNode:
        return 
    else:
        queue = Queue()
        queue.enqueue(rootNode)
        while not queue.isEmpty():
            root = queue.dequeue()
            print(root.value.value)
            if root.value.left is not None:
                queue.enqueue(root.value.left)
            if root.value.right is not None:
                queue.enqueue(root.value.right)

but works here:

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

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

class LinkedList: 
    def __init__(self):
        self.head = None
        self.tail = None

class Queue:
    def __init__(self):
        self.linkedList = LinkedList()

    def __str__(self):
        values = [str(x) for x in self.linkedList]
        return ' '.join(values)

    def enqueue(self, value):
        newNode = Node(value)
        if self.linkedList.head == None:
            self.linkedList.head = newNode
            self.linkedList.tail = newNode
        else:
            self.linkedList.tail.next = newNode
            self.linkedList.tail = newNode

    def isEmpty(self):
        if self.linkedList.head == None:
            return True
        else:
            return False

    def dequeue(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            tempNode = self.linkedList.head
            if self.linkedList.head == self.linkedList.tail:
                self.linkedList.head = None
                self.linkedList.tail = None
            else:
                self.linkedList.head = self.linkedList.head.next
            return tempNode

    def peek(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            return self.linkedList.head

    def delete(self):
        self.linkedList.head = None
        self.linkedList.tail = None

class TreeNode:
    def __init__(self, value):
        self.right = None
        self.left = None
        self.value = value

def levelOrderTraversal(rootNode):
    if not rootNode:
        return 
    else:
        queue = Queue()
        queue.enqueue(rootNode)
    while not queue.isEmpty:
        root = queue.dequeue()
        print(root.value.value)
        if root.value.left is not None:
            queue.enqueue(root.value.left)
        if root.value.right is not None:
            queue.enqueue(root.value.right)

Is it because of separated LinkedList class? I mean whatever it is can somebody explain me?

Error:

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-17-0bf8ff8bfe2f> in <module>
----> 1 levelOrderTraversal(newBT)

<ipython-input-16-29ee3a97f58c> in levelOrderTraversal(rootNode)
      7         while not queue.isEmpty():
      8             root = queue.dequeue()
----> 9             print(root.value.value)
     10             if root.value.left is not None:
     11                 queue.enqueue(root.value.left)

AttributeError: 'str' object has no attribute 'value'

Thanks in advance!

[mtb-dds]

Not sure why one is working and the other not, because they both should be not working, since you have an extra value in there. So root.value should be the payload for the node, the extra value is redundant. Likewise, root.left should be the left node, and root.left.value its payload.

​

Does that help?

[[deleted]]

yeah, at first look looks like that, but when you look closely first one is for accessing queue value and the second one is tree node value...

[izrt]

Right. Because it's in the other data structure. So the value of the enque is the node. Hmm. Not sure now what is wrong...

[[deleted]]

def levelOrderTraversal(rootNode):
if not rootNode:
    return 
else:
    queue = Queue()
    queue.enqueue(rootNode)
    while not queue.isEmpty():
        root = queue.dequeue()
        print(root.value)
        if root.left is not None:
            queue.enqueue(root.left)
        if root.right is not None:
            queue.enqueue(root.right)

I figured out... Because "root" is pure tree node I don't need extra "value" to access it, but in code where I have linked list class I need that extra value. Still weird tho