CODEWITHSUNDEEP
javarecursiontreebinary-search-tree
shawnin damnen
shawnin damnen

Reputation: 323

Checking if sum exists in tree path using recursion

I was trying to solve a question in trees where we had to check whether a complete path (root-to-leaf) would lead to a sum value (given by the user). I successfully managed to do it and here's the code

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)
        {
            return false;
        }
        sum = sum - root.val;
        if(sum==0 && root!=null && root.left==null && root.right==null)
        {
            return true;
        }
        boolean b1 = hasPathSum(root.left,sum);
        boolean b2 = hasPathSum(root.right,sum);
        return b1||b2;
    }
}

The main issue I have in understanding the code is that the sum would change as we move down the recursive function of root.left which should end up changing the value of sum when it is passed in the root.right statement. We would want the sum value passed in the second function to be the value at that given point (which should be changed due to sum being passed through the first function) but this code still seems to function properly.

Upvotes: 0

Views: 124

Answers (3)

Rorke miu
Rorke miu

Reputation: 11

The type of sum int is declared as a primitive. In Java,when you call a method with args,the method will get a copy of the value of the args.Primitive type would get the copy of value,but the class instance(object),method would get the copy of reference to the object.

Upvotes: 1

S3lvatico
S3lvatico

Reputation: 264

Your "sum" (the formal parameter of the method signature) is declared as a primitive type. This ensures that its value exists only in the current stack frame. Should it be changed along the recursion chain, that change would be confined to the frame the recursive call has taken place.

Each method invocation "sees" its own copy and value of the sum variable until the method returns a value, and passes the updated value down the recursion chain.

Upvotes: 0

Nishit
Nishit

Reputation: 1354

The beauty of recursion is that when the stack unwinds, it will have the same value as the method in which it is currently.

A stack is, well, like a stack. So the method on the top is the one which is currently being executed. Whenever a new method is being executed, the earlier method and it's state are frozen. So, in the below stack description, when Latest Call is called, there is no change in the methods below it.

hasPathSum(root.left.left, sum - root.val - root.left.val); --> Latest Call
hasPathSum(root.left, sum - root.val); --> Mid Call
hasPathsum(root, sum); --> First Call

Upvotes: 0

Related Questions