How to return all possible paths of random binary tree in Python

Question

I have a random binary tree in the following forms

12

13, 14

29, 26, 89

Each node has two children i.e ( 12->(13, 14), 13->(29, 26), 14 ->(26, 89)). Here I need to return all possible paths in the forms [ [12, 13, 29], [ 12, 13, 26], [12, 14, 26], [12, 14, 89]]. I tried with the following code. I have problem with updating list. Thanks in advance.

class Tree:

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

    def __str_(self):
        return '%s' % self.data

def makeList(tree, path =[]):
    if(tree != None):
        path.append(tree.data)
        if tree.left:
            path.append(makeList(tree.left, path))
        if tree.right:
            path.append(makeList(tree.left, path))

    return path

root = Tree(12)

root.left = Tree(13)

root.right = Tree(14)

root.right.left = Tree(26)

root.left.right = Tree(26)

root.left.left = Tree(29)

root.right.right = Tree(86)

x = makeList(root)

If 26 is connected both to 13 and 14 this is not a binary tree! (in a binary tree each node has, at most, one parent). — Nir Alfasi
– Nir Alfasi, Commented Sep 15, 2014 at 3:19

fishiwhj · Accepted Answer · 2014-09-15 08:50:43Z

5

I don't know how to solve it using a memoized recursion. But I still post my answer since it may solve your problem partly.

def makeList(tree):
    paths = []
    if not (tree.left or tree.right):
        return [[tree.data]]
    if tree.left:
        paths.extend([[tree.data] + child for child in makeList(tree.left)])
    if tree.right:
        paths.extend([[tree.data] + child for child in makeList(tree.right)])
    return paths

answered Sep 15, 2014 at 8:50

fishiwhj

8892 gold badges12 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

lucasmullerm · Accepted Answer · 2014-09-15 15:23:17Z

0

When you set this:

def makeList(tree, path =[]):

This empty list after path is not deleted after the execution of the function, if you call makeList a second time without a path parameter, the path list you had at the end of the first call will remain.

Consider the function:

def f(l=[]):
    l.append(17)
    print l

If you keep on calling f() without the parameter l you will get another 17 each time.

[17]
[17, 17]
[17, 17, 17]

edited Sep 15, 2014 at 15:23

answered Sep 15, 2014 at 3:20

lucasmullerm

1626 bronze badges

1 Comment

Aarav Over a year ago

Here how function can be a list even without its return list?.

Collectives™ on Stack Overflow

How to return all possible paths of random binary tree in Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related