How does parameters of a method get stored in stack during a recursive call?

I was doing a leetcode question https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/ and I am confused on how parameters for a method get stored during a recursive call.

If a node gets visited, I wanted to save it’s state that it was visited. When I send two variables, when the stack is getting unwinded the updated variable values are being lost.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean val1 = false, val2 = false;
        System.out.println("val1 - "+val1+" val2 - "+val2);
        System.out.println();

        TreeNode node = lca(root, p, q, val1, val2);
        System.out.println();
        System.out.println("val1 - "+val1+" val2 - "+val2);

        if(val1==true && val2==true)
            return node;
        return null;
    }
    
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q, boolean val1, boolean val2) {
        if(root==null) 
            return root;
        else if( p==root){
            val1 = true;
            System.out.println("val1 - "+val1+" val2 - "+val2);
            return root;
        } 
        else if( root==q){
            val2 = true;
            System.out.println("val1 - "+val1+" val2 - "+val2);
            return root;
        } 

        TreeNode left = lca(root.left, p, q, val1, val2);
        TreeNode right = lca(root.right, p, q, val1, val2);
        
        if(left==null && right==null) return null;
        else if(left==null) return right;
        else if(right==null) return left;
        else return root;
    }
}

Output -
val1 - false val2 - false

val1 - true val2 - false
val1 - false val2 - true

val1 - false val2 - false

But if I send an array and update values inside the array and pass the array itself as a parameter during recursion then the updated variable values are getting persisted.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean res[] = new boolean[2];
        //boolean val1 = false, val2 = false;
        System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
        System.out.println();

        TreeNode node = lca(root, p, q, res);
        System.out.println();
        System.out.println("val1 - "+res[0]+" val2 - "+res[1]);

        if(res[0]==true && res[1]==true)
            return node;
        return null;
    }
    
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q, boolean res[]) {
        if(root==null) 
            return root;
        else if( p==root){
            res[0] = true;
            System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
            return root;
        } 
        else if( root==q){
            res[1] = true;
            System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
            return root;
        } 

        TreeNode left = lca(root.left, p, q, res);
        TreeNode right = lca(root.right, p, q, res);
        
        if(left==null && right==null) return null;
        else if(left==null) return right;
        else if(right==null) return left;
        else return root;
    }
}

Output - 

val1 - false val2 - false

val1 - true val2 - false
val1 - true val2 - true

val1 - true val2 - true

I feel like I am missing some basic knowledge here, can anyone please help me understand how the two code’s are different and any material I can read to improve my knowledge on stack and recursion?

Answer

The issue has less to do with “recursion” and more to do with the function call itself.

When you’re calling foo(var1, var2), the variables get passed by value. The changes you make inside the function block aren’t propagated outside the function.

When you pass the array, it gets passed by reference/pointer. Any modifications made to it are made to it’s actual memory, so the changes gets retained/reflected even outside the function block.

You can read more on the differences between passing by value and reference here.

Edit:
Java is “always” pass-by-value because objects have references which are getting passed by value. This confusing terminology is clarified here in detail.

Advertisement

Answer