Why are the function parameters not being updated inside recursive python function?

Question

I was trying to find the inorder successor of node in a Binary Search Tree. My code is basically doing an inorder traversal and keeping track of the next node by using a counter variable:

class Solution:
    # returns the inorder successor of the Node x in BST (rooted at 'root')
    ans = None 
    def inorderSuccessor(self, root, x):
        counter = 0
        answer = self.findNode(root, x, counter)
        return self.ans
     
    def findNode(self, root, x, counter):
        if root == None:
            return None
        self.findNode(root.left, x, counter)
        if counter == 1:
            counter += 1
            self.ans = root
            return root
        if root.data == x.data:
            ###counter becomes 1 here, when it finds the x node.
            counter += 1
        ###but it is not updated in the params.    
        self.findNode(root.right, x, counter)

This does not work because the counter variable is never updated by the recursive call.

But if I make counter a global variable, it works:

class Solution:
    # returns the inorder successor of the Node x in BST (rooted at 'root')
    ans = None 
    counter = 0
    def inorderSuccessor(self, root, x):
        # Code here
        answer = self.findNode(root, x)
        return self.ans
     
    def findNode(self, root, x):
        if root == None:
            return None
        self.findNode(root.left, x)
        if self.counter == 1:
            self.counter += 1
            self.ans = root
            return root
        if root.data == x.data:
            self.counter += 1
        self.findNode(root.right, x)

Can anyone please explain this property of Python? Why doesn't it update the function parameters while making a recursive call?

Answer 1

When you call findNode(root, x, counter), then if findNode assigns a new value to counter, this is an assignment to the variable that is local to findNode -- the parameter variable. Such assignment is not to this counter variable that is named in the function call.

More to the algorithm: it is not necessary to have such a counter variable. You can instead use the following algorithm:

Walk down the tree according to the BST logic. When the x.data is less than the current node's data, then go left, else go right. Every time you go left, keep track of where you came from, as it might turn out to be the successor we are looking for.

Once you reach the end of this downward path in the tree, recall which node was the last node where the decision was to go left. That is the successor.

Code:

    def inorderSuccessor(self, root, x):
        candidate = None
        while root:
            if x.data < root.data:
                candidate = root
                root = root.left
            else:
                root = root.right
        return candidate