I'm trying to traverse a non-binary tree. A string representation of the tree, as a list, is:

['TOP', ['S', ['NP', ['PRP', 'I']], ['VP', ['VBP', 'need'], ['NP',['NP', ['DT', 'a'], ['NN', 'flight']], ['PP', ['IN', 'from'], ['NP',['NNP', 'Atlanta']]], ['PP', ['TO', 'to'], ['NP', ['NP', ['NNP','Charlotte']], ['NP', ['NNP', 'North'], ['NNP', 'Carolina']]]], ['NP',['JJ', 'next'], ['NNP', 'Monday']]]]]]

This is from the Penn Treebank. Ultimately, I'd like to turn this into a binary tree, but first I need a way to traverse the tree, as-is.

def traverse(tree_of_lists):for item in tree_of_lists:if isinstance(item, list):for x in traverse(item):yield xelse:yield item

This is the "basic" solution -- can run in Python 2.7 and gives you an iterable that you can simply loop on. (In recent Python 3.* versions you'd use yield from item instead of the inner for loop).

The isinstance test is unpleasant but depending on your exact problem it may be the only way to distinguish a "scalar item" from a "sub-tree". There may be better ones but you don't give us enough information to be able to tell. For example, if all "leaves" (scalars) are strings, you might prefer to check for that (still an isinstance check, alas!).