3

Im using a binary tree described in this book problem solving with algorithms and data structures

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

There is already a preorder 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 a return value of the list of nodes visited. So I can do something like

for i in preorder(tree):
    etc...

Im having trouble returning a list from a recursive method. The recursion stops as soon as it hits the 'return' I've tried variations using

return [tree.self.key] + preorder()

Or

yield ...

Any ideas?

Improve this question
2
  • What error are you getting? Is it something about concatenating None and list? Commented Apr 18, 2015 at 14:52
  • 1
    1). It appears that preorder() is a helper function and not actually a method of the BinaryTree class, so calling it a method is a little confusing. 2). If tree is an instance of BinaryTree, then tree.self.key is wrong. 3). In Python you rarely need getter (or setter) methods, you just access the attributes directly. Eg, preorder(tree.leftChild). Commented Apr 18, 2015 at 14:58

4 Answers 4

Reset to default
5

Are you sure you want tree.self.key and not simply tree.key when you print?

Otherwise, a 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 simple 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 transforms the function into a generator function; in particular, if you want an actual list (for indexing, slicing, or displaying for instance), you'll need to explicitly create it: list(preorder(tree)).

If you have a varying number of children, it's easy to adapt:

def preorder(tree):
    if tree:
        yield tree
        for child in tree.children:
            yield from preorder(child)
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Since you're directly accessing tree.key, you might as well use preorder(tree.leftChild) and preorder(tree.getRightChild). In addition, you should mention that to get the list of nodes this way you'd need to do something like nodes = list(preorder(tree)) or nodes = [node for node in preorder(tree)].
Thanks for the suggestion about the list. As for your other point, I'm accessing tree.key because I don't want to guess if there is a getKey() method but I believe that OP's tree.self.key might be faulty. There is already a comment about the lack of need of getters and setters in Python but here it's really besides the point.
I mentioned showing how to create a list because of the title of the question. Also note that it should be print tree.key, not yield tree.key — the OP wants a list of nodes, not one with a mixture of nodes and keys.
There was no nodes but only keys (by induction: preorder only yielded tree.key or what preorder yielded). But indeed OP seems to want a list of nodes so I've edited for yield tree.
2

You have to actually return a value from the recursive function (currently, it's just printing values). And you should build the list as you go, and maybe clean the code up 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)
Improve this answer

1 Comment

Thanks very much for the replies. I'm using python v3.4, I didn't get the yield expression working, Im still a bit lost between iterators and generators... Anyway this 'if not tree return empty list' fixes the problem I was having with 'can not + NoneType'
1

You can add second argument to preorder function, something like

def preorder(tree, visnodes):
    if tree:
        visnodes.append(tree.self.key)
        print(tree.self.key)
        preorder(tree.getLeftChild(), visnodes)
        preorder(tree.getRightChild(), visnodes)

...
vn = []
preorder(tree, vn)
Improve this answer

Comments

0

You can simply return a concatenated list for each recursive call, which combines the current key, the left subtree and the 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 []
Improve this answer

3 Comments

Thanks for your reply works perfectly. Just wandering if its not a binary tree how can I loop over all the children e.g. def preorder(tree): if tree: return [tree.key] + [preorder(child, msg) for child in tree.children]
@DamianSavage Yeah, but using list comprehension here would lead to a list of lists, since each preorder call returns a list. You can use a loop to to achieve this. I'll update my answer with that.
Instead of explicitly looping you can use sum: return sum((preorder(child) for child in tree.children), [tree.key]).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.