Printing all paths from a binary tree with python

Question

So I have a pretty dumb question that I can't seem to figure out. I'm just trying to print all paths and how they are being formed from a binary tree using preorder traversal. For that I'm storing each value on a data structure. My question is, why does the behavior change when using string vs using a list when storing each value on the way?

For a Binary Tree with the following definition:

class BinaryTree:
    def __init__(self, value, left_child=None, right_child=None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

left_branch = BinaryTree(5, BinaryTree(3, BinaryTree(7), BinaryTree(10)))
right_branch = BinaryTree(8, None, BinaryTree(4, BinaryTree(6), BinaryTree(9)))
root_tree = BinaryTree(1, left_branch, right_branch)

That would look like this:

When using a string to store and print the values:

def dfs(root, path):
    if root:
        path += str(root.value)
        print(path)
        dfs(root.left_child, path)
        dfs(root.right_child, path)

dfs(root_tree, '')

I get an output:

1
15
153
1537  <-- 1st
15310 <-- 2nd
18
184
1846  <-- 3rd
1849  <-- 4rd

That's ok.

But when I use a list:

def dfs(root, path):
    if root:
        path.append(root.value)
        print(path)
        dfs(root.left_child, path)
        dfs(root.right_child, path)

dfs(root_tree, [])

It doesn't seem to be doing the same thing as it is just storing all nodes on the same path:

[1]
[1, 5]
[1, 5, 3]
[1, 5, 3, 7]                 <-- 1st
[1, 5, 3, 7, 10]             <-- ???
[1, 5, 3, 7, 10, 8]
[1, 5, 3, 7, 10, 8, 4]
[1, 5, 3, 7, 10, 8, 4, 6]
[1, 5, 3, 7, 10, 8, 4, 6, 9]

I can't seem to understand why this is happening.

Yes, but also store each node value on a structure so that I can print the paths of the tree. — Miguel Ángel
– Miguel Ángel, Commented Feb 13, 2021 at 4:31
Was there reason, you switched from string to list data structure? — Cloud Cho
– Cloud Cho, Commented Oct 7, 2024 at 15:57
@CloudCho not really. I was just experimenting and trying to understand different data structures and their outputs. — Miguel Ángel
– Miguel Ángel, Commented Oct 15, 2024 at 1:30

Rishabh Kumar · Accepted Answer · 2021-02-13 04:17:14Z

4

This is happening because string is an immutable type, while list is mutable.

Now when you pass the strings in the functions (recursively) whenever it gets modified a new instance of the string is created, cause the original string can't be modified. Strings are immutable

However in a list, the modifications done on a list doesn't create a new instance, across the function calls. Python doesn't mind changing the original list, because lists can be modified. Lists are mutable.

This behavior of python while handling lists, can be said to be memory optimization, can also be said to be a pure essence of OOP.

To do the same with list just change the code like this:

def dfs(root, path):
    if root:
        path.append(root.value)
        print(path)
        dfs(root.left_child, path.copy())
        dfs(root.right_child, path.copy())

dfs(root_tree, [])

copy() creates a new list object with non-shared memory with original list

However, doing this makes the program consume more memory than it did before.

answered Feb 13, 2021 at 4:17

Rishabh Kumar

2,4403 gold badges15 silver badges23 bronze badges

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

2 Comments

Miguel Ángel Over a year ago

Thank you so much for your help and the detailed explanation. It helped me a lot.

Cloud Cho Over a year ago

Would you add explanation of "pure essence of OOP"? I never heard this. It sounds like Python language isn't good for reclusive algorithm.

Collectives™ on Stack Overflow

Printing all paths from a binary tree with python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related