Why does this simple recursive tree traversal algorithm fail?

user_10608218 0
Viewed 40

I've written a recursive algorithm to traverse nested iterators in Python. I don't understand why it succeeds in printing out the elements, but fails to yield them as a generator.

While I have managed to print out the elements:

tree = [[1,2],[3,[['abcde',['f']],'gh']]]

def traverse_printing(parent): 
     try: 
         for child in parent: 
              traverse(child) 
     except TypeError: 
         print(parent) 

>>> traverse_printing(tree)                                                                                                                                                                                    
1
2
3
a
b
c
...

I am struggling to turn it into a generator. 

def traverse(parent): 
     try: 
         for child in parent: 
              traverse(child) 
     except TypeError: 
         yield parent

traverse(tree) currently does not work. The result is:

>>> list(traverse(tree))                                                                                                                                                                              
[]

The expected result would be [1,2,3,'a','b','c','d','e','f','g','h']

Why is it the case? Many thanks

traversal tree generator nested python
1 Answers

traverse returns a generator object. Thus, on the traverse call, you have to loop over the returned result and yield each value or utilize the statement yield from :

for child in parent: 
   yield from traverse(child)

However, your current solution fails with a RecursionError: maximum recursion depth exceeded because you are only catching the occurrence of iteration over an integer value (which raises a TypeError). Looping over a string is a valid operation in Python, hence the infinite recursive calls. Thus you will need to check the actual types of parent:

def traverse(parent): 
  if isinstance(parent, str):
     yield from parent
  elif isinstance(parent, int):
     yield parent
  else: 
     for child in parent: 
        yield from traverse(child) 

list(traverse(tree))

Output:

[1, 2, 3, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
user_73267380
Related