Python returns list from recursive method
Im using the binary tree described in this book solving problems with algorithms and data structures
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
There is already a traversal method defined as follows.
def preorder(tree):
if tree:
print(tree.self.key)
preorder(tree.getLeftChild())
preorder(tree.getRightChild())
I just want to add the return value of the list of visited nodes. So I can do something like
for i in preorder(tree):
etc...
I am having trouble returning a list from a recursive method. Recursion stops as soon as it hits "return". I tried options with
return [tree.self.key] + preorder()
or
yield ...
Any ideas?
source to share
Do you really want tree.self.key
and not just tree.key
when printing?
Otherwise, solution with yield from
(Python 3.3+):
def preorder(tree):
if tree:
yield tree
yield from preorder(tree.getLeftChild())
yield from preorder(tree.getRightChild())
Or with a simple one yield
:
def preorder(tree):
if tree:
yield tree
for e in preorder(tree.getLeftChild()):
yield e
for e in preorder(tree.getRightChild()):
yield e
Note that using yield
or yield from
converting a function to a generator function; in particular, if you need an actual list (for indexing, slicing or display for example), you need to explicitly create him list(preorder(tree))
.
If you have a different number of children, it's easy to adapt:
def preorder(tree):
if tree:
yield tree
for child in tree.children:
yield from preorder(child)
source to share
You should actually return the value from the recursive function (currently it just prints the values). And you should create the list as you go, and maybe clean up the code a bit - something like this:
def preorder(tree):
if not tree:
return []
# optionally, you can print the key in this line: print(self.key)
return [tree.key] + preorder(tree.leftChild) + preorder(tree.rightChild)
source to share
You can simply return a concatenated list for each recursive call that concatenates the current key, left subtree, and right subtree:
def preorder(tree):
if tree:
return ([tree.key] + preorder(tree.getLeftChild()) +
preorder(tree.getRightChild()))
return []
For an n-ary tree:
def preorder(tree):
if tree:
lst = [tree.key]
for child in tree.children:
lst.extend(preorder(child))
return lst
return []
source to share