Level order traversal binary tree using two queues

Question

Leetcode problem: https://leetcode.com/problems/binary-tree-level-order-traversal/

I have two queues, I empty my first queue (q) while adding elements to my second queue (q2) , this way i can get the levels. When the first queue is empty I pass it in to function to create the ArrayList of that level and add to my result value, if q2 is empty that means there was nothing that was added so we can break out of the loop and return the function. I have to manually add in the first node. The problem is that only the middle level is being added, and not the rest.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return null;
        }
        
        List<List<Integer>> returnList = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        List<Integer> tempList = new ArrayList<>();
        tempList.add(root.val);
        returnList.add(tempList);
        
        while(true) {
            Queue<TreeNode> q2 = new LinkedList<>();
            while(!q.isEmpty()) {
                TreeNode node = q.remove();
           
                if(node.left != null) {
                    q2.add(node.left);
                }
                if(node.right != null) {
                    q2.add(node.right); 
                }
            }
            
            if(q2.isEmpty()) {
                break;
            }
  
            q = q2;
            addList(returnList, q2);
       
        }
        return returnList;
    }
    
    public static void addList(List<List<Integer>> returnList, Queue<TreeNode> q2) {
        List<Integer> tempList = new ArrayList<>();
        int size = q2.size();
        for(int i = 0; i < size; i++) {
            int val = q2.remove().val;
            System.out.println(val);
            tempList.add(val);
        }
        returnList.add(tempList);
    }
}

trincot trincot · Accepted Answer · 2020-11-02T12:30:25

The problem relates to this part of the code:

    q = q2;
    addList(returnList, q2);

The function addList will empty the given queue q2, calling remove on it. As q has become a reference to the same queue, you have emptied q, and so the next iteration of the outer loop will not get into the inner loop, and exit the outer loop with a break.

To avoid this from happening, make sure that the remove calls are not executed on q: make a copy:

    q = new LinkedList<>(q2);
    addList(returnList, q2);

or, alternatively:

    q = q2;
    addList(returnList, new LinkedList<>(q2));

Level order traversal binary tree using two queues

1 Answers