Empty output while performing level order traversal in Binary trees in Java

Question

I wanted to perform level order traversal in Binary Trees in Java. Basically I needed to store values of nodes of each level in an array list and store such different array lists in one single array list. In my final output, only empty array lists are being shown. I can not understand the logical error. Can anyone please guide me.

public class Solution {
        static ArrayList<ArrayList<Integer>> ourList=new ArrayList<>();
        static ArrayList<Integer>ourArray=new ArrayList<>();
        public static void breadth(Node root){
            Queue<Node> ourQueue=new LinkedList<>();
            ourQueue.add(root);
            while(!ourQueue.isEmpty()){
                int size=ourQueue.size();
                for(int i=0;i<size;i++){
                    Node poppedElement=ourQueue.poll();
                    ourArray.add(poppedElement.data);
                    if(poppedElement.left!=null){
                        ourQueue.add(poppedElement.left);
                    }
                    if(poppedElement.right!=null){
                        ourQueue.add(poppedElement.right);
                    }
                }
                ourList.add(ourArray);
                ourArray.clear();
            }
        }
    }

Answer 1

Do the following short test:

    ArrayList<ArrayList<Integer>> ourList=new ArrayList<>();
    ArrayList<Integer>ourArray=new ArrayList<>();
    //add values
    ourArray.add(1);  ourArray.add(2);  ourArray.add(3);  ourArray.add(4);
    ourList.add(ourArray);

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray.clear();
    System.out.println(ourList.get(0)); //prints []

The reason is that ourList contains a reference to a list. ourArray is a reference to the same list, and when it is cleared, ourList contains a reference to an empty list.

Now test the solution proposed by PHolzwarth:

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray = new ArrayList<>();
    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]

An alternative solution is a "defensive copy":

    ourList.add(new ArrayList<>(ourArray)); //add a copy of ourArray

    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]
    ourArray.clear();
    System.out.println(ourList.get(0)); //prints [1, 2, 3, 4]