pythonarraysstringbinary-treedepth-first-search

Difference between passing in string vs. array parameters to recursive function


This may be a dumb question so I am sorry, but there is a Leetcode problem where you have to return all of the paths from the root node to leaf nodes in an array of strings connected with "->" (example answer: ["1->2->5", "1->3"]). Both of the solutions in the code blocks below work. I am mainly curious why for the string solution I can just return once I have appended the path and then the next recursion call isn't impacted but for the array solution I cannot return since I have to pop the current element off or it will impact the next recursion call.

Is this because arrays are mutable so the array itself changes whereas strings are not and it creates a copy to get passed in?

This is the solution creating a string.

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        def dfs(node, currPath):
            if not node:
                return
            
            currPath += str(node.val)
            if not node.right and not node.left:
                res.append(currPath)
                return
            
            dfs(node.left, currPath + "->")
            dfs(node.right, currPath + "->")
        
        dfs(root, "")
        return res

And this is the solution creating an array and then joining it to make the string.

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        def dfs(node, currPath):
            if not node:
                return
            
            currPath.append(str(node.val))
            if not node.right and not node.left:
                res.append("->".join(currPath))
            
            dfs(node.left, currPath)
            dfs(node.right, currPath)
            currPath.pop()
        
        dfs(root, [])
        return res

Solution

  • This difference in behavior is due to the nature of mutable vs. immutable objects:

    However, if you insist to pass an array to your function, and don't want to impact the original array, you can pass a copy of the list/array:

    foo(my_list.copy())