CODEWITHSUNDEEP
pythondepth-first-search
Claudiu Creanga
Claudiu Creanga

Reputation: 8386

How come these 2 implementations of dfs give different results?

This one gives the correct result:

def binaryTree(root):
    paths = []

    def dfs(root, path=""):
        if root:
            if path != "":
                path += "->"
            path += str(root.val)
            if not root.left and not root.right:
                paths.append(path)
            dfs(root.left, path)
            dfs(root.right, path)

    dfs(root)
    return paths # gives ['1->2->4', '1->2->5', '1->3']

And in this one the list of path keeps growing:

def binaryTree2(root):
    paths = []

    def dfs(root, path=[]):
        if root:
            path.append(root.val)
            if not root.left and not root.right:
                paths.append("->".join(map(str, path)))
            dfs(root.left, path)
            dfs(root.right, path)

    dfs(root)
    return paths # gives ['1->2->4', '1->2->4->5', '1->2->4->5->3']

The tree is like this: <1, <2, <4, None, None>, <5, None, None>>, <3, None, None>>

The only difference is that in one I concatenate strings and in the other I append to list.

Upvotes: 0

Views: 161

Answers (1)

Muts
Muts

Reputation: 145

So in the first implementation: All path += ... statements essentially create a new string and have path point to it.

As for the second implementation you have a single list that is passed around all the time. You should pop back the node right before dfs returns.

def binaryTree2(root):
    paths = []

    def dfs(root, path=[]):
        if root:
            path.append(root.val)
            if not root.left and not root.right:
                paths.append("->".join(map(str, path)))
            dfs(root.left, path)
            dfs(root.right, path)
            path.pop() # this clears your stack as your functions return

    dfs(root)
    return paths

Edit: Python strings are immutable - i.e. once created, they can't be modified.

# below line essentially creates a pointer,
# and a string object that `path` points to.
path = "huhu"

# this creates another string object `huhu123`.
# So at this point we have 3 strings objects,
# "123", "huhu" and "huhu123". And a pointer `path` if you will.
# `path` points to "huhu123"
path += "123"

If we had more innocent objects instead of strings, once they are left with no references, they'd be garbage collected. Strings get special treatment, in our case all 3 of them are interned.

Upvotes: 2

Related Questions