Akt Akt - 1 month ago 7
Python Question

Return int from generators - Python

I have been trying to figure out a way to yield an int value from a generator but the scripting engine is throwing errors at me.

def inorderTraversal(self, node):
if(node.left):
for n in self.inorderTraversal(node.left):
yield n[0]
yield node.data[0]
if(node.right):
for n in self.inorderTraversal(node.right):
yield n[0]


The error is:


File "ac.py", line 142, in inorderTraversal

yield n[0] TypeError: 'int' object is not subscriptable


where

n = {10,"X"}
. I tried to search it but no solution I know of caters to my needs.

Answer

if your yield node.data[0] is correct, then when you do yield n[0] in the recursive case is like you are doing yield node.data[0][0] in that branch. So change it to yield n instead because the recursive case already give you what you need, you only need to pass it along.

Furthermore, when designing a tree you usually do it in a way that .data store, well, the data that the user of your tree want to store in it and don't worry about what that is or how it looks, so you usually do yield node.data.

Also as you are in python 3, you can use the yield from that is a shortcut for that kind of for-loop.

with those in mind your code should look like this

def inorderTraversal(self, node):
    if node.left:
        yield from self.inorderTraversal(node.left)
    yield node.data
    if node.right:
        yield from self.inorderTraversal(node.right)

as you have not provided with a Minimal, Complete, and Verifiable example of your problem I can only guess, so

Lets see a example tree code like this

class Node:
    def __init__(self, data, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

with that lets build a sample tree like the one in wikipedia

sample tree

test1 = Node(6,
             Node(2,
                  Node(1),
                  Node(4,
                       Node(3),
                       Node(5)
                       )
                  ),
             Node(7,
                  None,
                  Node(9,
                       Node(8)
                       )
                  )
             )

lets do it again with your data structure of [int,str]

test2 = Node([6,"F"],
            Node([2,"B"],
                 Node([1,"A"]),
                 Node([4,"D"],
                      Node([3,"C"]),
                      Node([5,"E"])
                      )
                 ),
            Node([7,"G"],
                 None,
                 Node([9,"I"],
                      Node([8,"H"])
                      )
                 )
            )

now the fun part, the inorder function, first yours

def inorderBad(node):
    if node.left:
        for n in inorderBad(node.left):
            yield n[0]
    yield node.data[0]
    if node.right:
        for n in inorderBad(node.right):
            yield n[0]

lets test it with test2

>>> list(inorderBad(test2))
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    list(inorderBad(test2))
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 26, in inorderBad
    for n in inorderBad(node.left):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 27, in inorderBad
    yield n[0]
TypeError: 'int' object is not subscriptable
>>> 

look familiar? the error as I said is the recursive case of n[0] when you reach the bottom Node (A in this case) it yield data[0] (1 in this case), in the Node above (B) it get this value and try to yield it again only this time try to yield the first value of it and fail in that regard as the error said

Now lets fix it

def inorder2(node):
    if node.left:
        for n in inorder2(node.left):
            yield n
    yield node.data[0]
    if node.right:
        for n in inorder2(node.right):
            yield n         

and test it

>>> list(inorder2(test2))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 

work as expected, lets try with the other one

>>> list(inorder2(test1))
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    list(inorder2(test1))
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 35, in inorder2
    for n in inorder2(node.left):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 35, in inorder2
    for n in inorder2(node.left):
  File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 37, in inorder2
    yield node.data[0]
TypeError: 'int' object is not subscriptable
>>> 

naturally it fail because inorder2 is not general enough, also in your current implementation, what if you want the string instead? have you think on that?, in general those concern should not be of relevance to this particular function, it should only provide all the data inorder

so the general inorder and adding the yield from is

def inorder(node):
    if node.left:
        yield from inorder(node.left)
    yield node.data
    if node.right:
        yield from inorder(node.right)

test

>>> list(inorder(test2))
[[1, 'A'], [2, 'B'], [3, 'C'], [4, 'D'], [5, 'E'], [6, 'F'], [7, 'G'], [8, 'H'], [9, 'I']]
>>> list(inorder(test1))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>