Which parameters are local in a binary tree recursion?

import java.util.*;


    public static void main(String[] args) {

        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(7);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(5);
        root.right.right = new TreeNode(4);
        List<Integer> list = postorderTraversal(root);
        System.out.println(list);
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        list = helper(root, list);
        return list;
    }

    private static List<Integer> helper(TreeNode node, List<Integer> list){
        if (node != null) {
            helper(node.left, list);
            helper(node.right, list);
            list.add(node.val);
        }
        return list;
    }
}

In this question, I don't understand why I don't have to do list = helper(node.left, list); Why is list global here and when I'm changing my root it's local and I have to do root.left = recurse(root.left) ?

2 answers

  • answered 2017-12-06 01:42 Klaus

    This is because of how pointers work in java. When you pass list in as a parameter to a function, you aren't passing in the object itself, you're passing in its memory address on your computer. This memory address is called a pointer and is useful because it lets you avoid expensively duplicating objects.

    You don't normally notice this because java typically hides the fact that it's using pointers at all. For instance, when you do list.add(...), it works like you're using an ordinary object and calling add() on it because java automatically substitutes the object for the pointer.

    So list is kind of like a global variable, because even though the pointer is copied every time you pass it into something, it still references the same section of memory. Changing that section of memory will affect what every other pointer to that spot sees, so you get changes that other functions can see.

  • answered 2017-12-06 03:43 Jim Garrison

    The statement

    List<Integer> list = new ArrayList<Integer>();
    

    Does two things. First it allocates a new ArrayList object on the heap. Then it stores a reference to that heap object in the local variable list. When you invoke helper, you are passing only the reference, which can be thought of as a memory address referring to the actual object on the heap. This reference gets passed down to the recursive invocations of helper. Each invocation gets a local copy of list, but this is only a copy of the reference, not the heap object. All those instances of list refer to the same heap object, the one you initially allocated. This is why it "feels" like it's global, but it is most definitely not.

    The same concept applies to the TreeNode references, in fact to all object references in Java.

    This can be highly confusing for new Java programmers. Java is "Pass-by-value", meaning that parameters are copied when invoking a method, but when the variables are objects, the "value" is a reference and not the object itself, and only the reference is copied. The only values that are copied for parameter passing are primitive values (boolean, char, int, long, float, double).