CODEWITHSUNDEEP
pythonarraysstringbinary-treedepth-first-search
Mike Carpinello
Mike Carpinello

Reputation: 5

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

Upvotes: 0

Views: 77

Answers (2)

Na Cer
Na Cer

Reputation: 1

When passing a string to a recursive function, the string is immutable, meaning it cannot be modified directly. Any changes result in the creation of a new string in each recursive call (e.g., using slicing or concatenation).When passing an array, the array is mutable, meaning it can be modified in place. You can either mutate the original array or pass a copy (e.g., by slicing), depending on the desired outcome.Key Difference:String: Immutable, changes create new strings.Array: Mutable, changes can modify the original array.

Upvotes: 0

Amir Farahani
Amir Farahani

Reputation: 106

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

  • Immutable objects (like strings) create new objects when modified.
  • Mutable objects (like lists) are modified in-place.

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())

Upvotes: 0

Related Questions