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

I have a random binary tree in the following forms

12

13, 14

29, 26, 89

Each node has two children ie (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've tried using the following code. I have a problem updating the 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)
```

```
+3

source to share

I don't know how to solve it using memoized recursion . But I leave my answer anyway, as it may partially solve your problem.

``````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
```

```
+2

source

When you install this:

``````def makeList(tree, path =[]):
```

```

This empty list after the path is not removed after the function is executed, if you call makeList a second time without a path parameter, the list of paths 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 calling f () without the l parameter, you will get 17 more each time.

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

```
0

source

All Articles