Getting an error in Binary Tree question: AttributeError: 'int' object has no attribute 'val'

Question

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return None

        li = []
        curr = root
        li.append([root.val])
        if curr.right and curr.left:
            li.append([self.levelOrder(curr.left.val), self.levelOrder(curr.right.val)])
        elif not curr.right and curr.left:
            li.append([self.levelOrder(curr.left.val)])
        elif curr.right and not curr.left:
            li.append([self.levelOrder(curr.right.val)])
#            elif not curr.right and not curr.left:
        else:
            return li

So for the question "102. Binary Tree Level Order Traversal" on LeetCode, I was writing the code. I'm a beginner so can't understand why I'm getting the following error:

AttributeError: 'int' object has no attribute 'val'
    li.append([root.val])

Even though the root is a Binary Tree node so it should return value yet it is throwing this error.

Tried working everything out but couldn't get any concrete reasoning for the issue.

Answer 1

There are several issues:

• The cause of the error is that you make the recursive call with an int as argument instead of a Node:

  self.levelOrder(curr.left.val)
  

  ... should be:

  self.levelOrder(curr.left)
  

• return None is not what is required. The challenge description says that for an empty tree you should return [].

• The return li statement should not only be executed in the else clause. You need to always return a list, so also in the other cases

• li.append([root.val]) will not append an int to the list, but a list. So that gives you a nested list. Here the square brackets should be removed

• li.append([self.levelOrder(curr.left.val)]) is even worse: the recursive call will return a list, and then you wrap that list in a list, and then you append that list of list as an item to the list -- this gives you three levels of nested lists which will accumulate as the tree gets larger. You should use the extend method instead.

• But even when all of the above is corrected, this is performing a pre-order traversal, not a level order traversal. A level order traversal algorithm has a completely different approach than a pre-order traversal, so almost nothing of your code can be reused. You must start from scratch and look into bread-first traversals.