Recursively searching an object and editing a string when found

I am new to python and having issues dealing with immutable strings. My problem is as follows:

I have a tree where each node is a dictionary and each node has variable number of children. I have multiple operations I wish to perform on this tree and therefore recursively traverse it.

The setup is that I have class that traverses the tree with the following function like so:

def __recursiveDive(self, node, enterFunc, leaveFunc, parentNode):
    if self.__break:
        return

    if not self.__skipNode:
        enterFunc(node, parentNode, self)
        if isinstance(node, dict):
            for key, value in node.items():
                self.__recursiveDive(value, enterFunc, leaveFunc, node)
        elif isinstance(node, list):
            for child in node:
                if isinstance(child, dict):
                    self.__recursiveDive(child, enterFunc, leaveFunc, node)

        leaveFunc(node, parentNode, self)
    else:
        self.__skipNode = False

enterFunc and leaveFunc are defined externally and perform the required work on the tree/node.

My issue is that since python strings are immutable I feel like I am unable to modify any string fields in the tree. The enterFunc, which is a function belonging to another class and is passed to the class is as follows:

def enter(self, node, parentNode, traverser):
    if isinstance(node, str):
        search = re.search(self.regexPattern, node)
        if search:
            node = node.replace(search.group(2),self.modifyString(search.group(2)))

The changes to node here are local only. Is my only solution to have the enter and leave functions return the node?

What is the correct/pythonic way to approach this problem?