Well Explained Code in JAVA || Use of ArrayList and Queues ✅
\n\n# Approach\nThis is a Java solution for the problem of traversing a binary tree level by level and returning the values of each level in a list of lists of 
\n\n# Approach\nThis is a Java solution for the problem of traversing a binary tree level by level and returning the values of each level in a list of lists of integers.\n\nThe solution uses a Queue to traverse the tree in a level-by-level fashion. The outer list of the resulting list of lists is represented as an ArrayList in this solution, while the inner lists are also represented as ArrayLists.\n\nHere is a step-by-step explanation of the code:\n1. Declare a Queue named q that will be used for level-by-level traversal of the binary tree.\n2. Declare a List of Lists of Integers named finalAns to store the final result.\n3. Check if the root of the binary tree is null. If it is, return the empty list of lists.\n4. Add the root node of the binary tree to the queue.\n5. While the queue is not empty, perform the following steps for each level of the tree:\n- Get the size of the current level of the queue.\n-  Create a new list to store the values of the current level.\n- For each node in the current level of the queue, add its left and right children (if they exist) to the end of the queue and add its value to the list of values for the current level.\n- Add the list of values for the current level to the final result list.\n6. Return the final result list of lists of values for each level of the binary tree.\n\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node in the tree exactly once, and the time taken to process each node is constant time.\n\n- Space complexity:\nThe space complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because in the worst case, the queue can store all the nodes of the last level of the binary tree, which is approximately half of the total number of nodes in the tree. Additionally, the space required for the output list of lists is also proportional to the number of nodes in the tree.\n\nTherefore, the overall time and space complexity of this solution are both O(n).\n\n# Note \nThe difference between using LinkedList and ArrayList for the outer list in this code is related to their internal data structures and their performance characteristics.\n\nLinkedList is implemented as a doubly linked list, where each node has a reference to its previous and next nodes. This makes it efficient to add or remove elements from the beginning or end of the list, but less efficient to access elements at arbitrary positions in the list. Therefore, using LinkedList for the outer list would be more efficient if we frequently add or remove elements from the beginning or end of the list.\n\n`  List<List<Integer>> finalAns = new LinkedList<List<Integer>>();`\n\nOn the other hand, ArrayList is implemented as a dynamic array, where elements are stored in a contiguous block of memory. This makes it efficient to access elements at arbitrary positions in the list, but less efficient to add or remove elements from the beginning or end of the list. Therefore, using ArrayList for the outer list would be more efficient if we frequently access elements at arbitrary positions in the list.\n\n`List<List<Integer>> finalAns = new ArrayList<List<Integer>>();`\n\nIn the case of the provided code, since we only add elements to the end of the outer list and do not access elements at arbitrary positions, using either LinkedList or ArrayList for the outer list should produce the **same results in terms of correctness**. However, using ArrayList may be more efficient in terms of memory usage and performance, especially for larger input trees, because it avoids the overhead of maintaining the linked list structure.\n\n\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public List<List<Integer>> levelOrder(TreeNode root) {\n        Queue<TreeNode> q = new LinkedList<>();\n        List<List<Integer>> finalAns = new ArrayList<List<Integer>>();\n        if(root==null){\n            return finalAns;\n        }\n        q.add(root);\n        while(!q.isEmpty()){\n            int levels = q.size();\n            List<Integer> subLevels = new ArrayList<>();\n            for(int i=0;i<levels;i++){\n                if(q.peek().left!=null){\n                    q.add(q.peek().left);\n                }\n                if(q.peek().right!=null){\n                    q.add(q.peek().right);\n                }\n                subLevels.add(q.remove().val);\n            }\n            finalAns.add(subLevels);\n        }\n        return finalAns;\n    }\n}\n```\n![upvote.jpeg](https://assets.leetcode.com/users/images/cbe9c1e4-efc6-4249-83c7-93a175d3533a_1678170362.456634.jpeg)\n
['Breadth-First Search', 'Binary Tree', 'Java']