Python: TypeError: 'TreeNode' object is not iterable

Question

Here's my code:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n==0:
            return []
        return self.generateTreesHelper(range(1, n+1))
    
    def generateTreesHelper(self, lst):
        if len(lst) == 0:
            return [None]
        elif len(lst) == 1:
            return TreeNode(lst[0])
        else:
            res = []
            for i in range(0, len(lst)):
                left_trees = self.generateTreesHelper(lst[:i])
                right_trees = self.generateTreesHelper(lst[i+1:])
                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(lst[i])
                        root.left = left
                        root.right = right
                        res.append(root)
            return res

The code is to generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,

Given n = 3, The program should return all 5 unique BST's shown below.

[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]].

However, I keep getting the error message.

TypeError: 'int' object is not iterable.

Answer 1

I don't know how you get that

TypeError: 'int' object is not iterable.

error. On both Python 2.6 and 3.6 I get the error mentioned in your question's title:

TypeError: 'TreeNode' object is not iterable

This is because return TreeNode(lst[0]) returns a TreeNode. It should return a list containing that TreeNode, so that it can be iterated over in your left_trees and right_trees for loops.

Here's a repaired version of your code, with a simple __repr__ method so that we can see that the output is correct.

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        if self.left is None and self.right is None:
            s = '{}'.format(self.val)
        else:
            s = '[val:{}, left:{}, right:{}]'.format(self.val, self.left, self.right)
        return s

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n==0:
            return []
        return self.generateTreesHelper(range(1, n+1))

    def generateTreesHelper(self, lst):
        if len(lst) == 0:
            return [None]
        elif len(lst) == 1:
            return [TreeNode(lst[0])]
        else:
            res = []
            for i in range(0, len(lst)):
                left_trees = self.generateTreesHelper(lst[:i])
                right_trees = self.generateTreesHelper(lst[i+1:])
                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(lst[i])
                        root.left = left
                        root.right = right
                        res.append(root)
            return res

print(Solution().generateTrees(3))

output

[[val:1, left:None, right:[val:2, left:None, right:3]], [val:1, left:None, right:[val:3, left:2, right:None]], [val:2, left:1, right:3], [val:3, left:[val:1, left:None, right:2], right:None], [val:3, left:[val:2, left:1, right:None], right:None]]