Binary tree BFS traversal - AttributeError: 'list' object has no attribute 'value'

Question

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

def level_order_traversal(root):
        q = []
        result = []
        if not root:
            return result
        q.append(root)
        while q:
            temp_q = []
            res_q = []
            node = q.pop(0)
            res_q.append(node.value)
            if node.left:
                temp_q.append(node.left)
            if node.right:
                temp_q.append(node.right)
            q = temp_q
            result.append(res_q)
        return result

if __name__ == "__main__":
    result = level_order_traversal([0, 1, None, None, 2, 4, None, None, 3])
    print(result)

Answer 1

Code challenge sites will often convert the JSON input into an instance of the given class -- in this case a BinaryTreeNode with nested instances of the same.

Once you decide to test your code outside the code challenge framework, you'll have to do that preparation yourself. If you want it to work with a list as input, then add this helper function to your toolset:

def to_binary_tree(items):
    if not items:
        return None

    it = iter(items)
    root = BinaryTreeNode(next(it))
    q = [root]
    for node in q:
        val = next(it, None)
        if val is not None:
            node.left = BinaryTreeNode(val)
            q.append(node.left)
        val = next(it, None)
        if val is not None:
            node.right = BinaryTreeNode(val)
            q.append(node.right)
    return root

And now you can do:

if __name__ == "__main__":
    result = level_order_traversal(to_binary_tree([0, 1, None, None, 2, 4, None, None, 3]))
    print(result)