Recursion: Does the variable passed to the function need to be tracked and updated?

I was going through the code of deleting a node from a binary search tree and I am a little confused

Node deleteRec(Node root, int key)
        /* Base Case: If the tree is empty */
        if (root == null)  return root;

        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);

        // if key is same as root's key, then This is the node
        // to be deleted
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            root.key = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);

        return root;

Why do we need to store the results of function calls in the root.left and root.right variables at several places? Since the value of root i.e the reference is being passed to the function, any changes in the subsequent call will automatically update the tree, isn’t it so? So why store the values in the variables? To make my point clear below is another piece of code

// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
                         Stack stack)
    // Mark the current node as visited.
    visited[v] = true;
    Integer i;

    // Recur for all the vertices adjacent to this
    // vertex
    Iterator<Integer> it = adj[v].iterator();
    while (it.hasNext())
        i =;
        if (!visited[i])
            topologicalSortUtil(i, visited, stack);

    // Push current vertex to stack which stores result
    stack.push(new Integer(v));

Here stack is being passed to the function and we are simply using it again and again in further function calls because we know that the stack will keep on updating across calls.

Am I missing something or did I understand something wrong? Can someone please help me understand. Thanks !!

When you delete a node of a tree, the parent node’s left or right pointer may need to be updated. The simplest case is when the deleted not is a leaf: in that case, the link that pointed to it must be set to null.

If in addition, the node that is deleted happens to be the root node, the pointer to the root must be updated.

When you’re calling the deleteRec method, you cannot know in advance whether or not the value returned will be the same as the first parameter.

The root object at different levels of recursion is not the same object.

When you recurse down the tree, you call deleteRec with root.left or root.right as the first argument. Hence, the next level of recursion will treat the root of the left or the right subtree as its “root”.

This is different from stack variable that you pass around for the third parameter of topologicalSortUtil: this variable is always passed down unchanged, so all levels have access to the same exact object.

When you delete a node, you must pull up the portion of the tree under it. Otherwise, you would delete the node and all its descendants, which is incorrect.

Your deleteRec method receives a Node of the binary tree and modifies the tree. However, each recursive call is passed a different Node of the tree. This is unlike your second example, where the same Stack is passed to each recursive call.

Now, when deleteRec finds the Node that it should delete from the tree (which happens when the root of the current recursive call is the Node that should be deleted), it can’t remove that Node from the tree. It must modify the parent Node of the removed Node in order to remove that Node from the tree. That’s what happens when the recursive call returns, and the Node returned by that call is assigned to either root.left or root.right.