Java Recursion Parameter Value

Question

From a binary tree, you want to create a 2-d arraylist where each arraylist within the main arraylist contains all the nodes of a binary tree on a single level, for all of the levels. I understand how to do this recursively with DFS but I am very confused about why it possible to get the correct answer by passing in the arraylist I want to populate as a parameter in the recursive function.

The header of my recursive function looks like this

createLevelLinkedList(TreeNode current, ArrayList<LinkedList<TreeNode>> lists, int level)

With basecase:

if (current == null) return;

As the tree is traversed, the current node will be appended to its corresponding arraylist within "lists". Within the recursive function there there two recursive calls to move the function to the child nodes of current:

createLevelLinkedList(current.left, lists, level + 1);
createLevelLinkedList(current.right, lists, level + 1);

Suppose there is a tree that looks like this

          5
     3         8
 2      4          9

With depth first tree traversal, after the first return, we will have TreeNode "2" is the top object in the stack, then "3". When TreeNode "3" is current and the function calls

    createLevelLinkedList(current.right, lists, level + 1);

To push TreeNode "4" onto the stack, how can lists contains TreeNode "2" if it actually does and what is really going in memory?

The code I am referencing can be found on Github: https://github.com/gaylemcd/ctci/blob/master/java/Chapter%204/Question4_4/QuestionDFS.java

public static void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) 
{
  if (root == null) return;
  LinkedList<TreeNode> list = null;
  if (lists.size() == level) { // Level not contained in list
    list = new LinkedList<TreeNode>();
/* Levels are always traversed in order. So, if this is the first time we've visited level i,
 * we must have seen levels 0 through i - 1. We can therefore safely add the level at the end. */
    lists.add(list);
  } else {
    list = lists.get(level);
  }
  list.add(root);
  createLevelLinkedList(root.left, lists, level + 1);
  createLevelLinkedList(root.right, lists, level + 1);
}

You didn't show the code in which you add nodes to your list, so how can we answer your question? Why don't you post the full code of createLevelLinkedList? — Eran
– Eran, Commented Dec 21, 2014 at 7:07
Yes, for sure. I'm looking at some code on GitHub github.com/gaylemcd/ctci/blob/master/java/Chapter%204/… — Arjun Patel
– Arjun Patel, Commented Dec 21, 2014 at 7:10

Eran · Accepted Answer · 2014-12-21 07:21:27Z

1

You should understand that there's only one ArrayList instance passed to the createLevelLinkedList method. Each recursive call to createLevelLinkedList receives a reference to the same instance of the ArrayList.

Therefore, once the TreeNode 2 is added to the ArrayList (or, to be exact, to one of the LinkedLists contained within the ArrayList), it stays there throughout the execution of the recursive method. It doesn't disappear when the invocation of createLevelLinkedList that added it to the list returns.

answered Dec 21, 2014 at 7:21

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Arjun Patel Over a year ago

I see. I think my main confusion comes from level not changing value in the previous stack frames after TreeNode 2 is added to lists. Is it because level is a primitive type?

Eran Over a year ago

@ArjunPatel Java is a pass by value language, so it doesn't matter whether you are passing a primitive or reference variable to a method. In both cases the method can only change the variable locally, which doesn't affect previous stack frames. The lists variable also remains unchanged. The thing that changes is the state of the lists object (as you add linked lists and elements to it).

Collectives™ on Stack Overflow

Java Recursion Parameter Value

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related