Why am I getting "time limit exceeded" error in binary tree level order traversal problem in leetcode?

I'm trying to solve the problem: Binary tree level order traversal problem on LeetCode and I've also tried looking for the answers, but I'm still getting a time limit exceeded (TLE) error. Please help me find out what is going wrong. I'm using Java to solve this problem.

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

We have to return the level order traversal in terms of List<List<Integer>>.

And here's my code for the same problem:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                level.add(q.peek().val);
                q.poll();
                if(root.left != null){
                    q.offer(root.left);
                }
                if(root.right != null){
                    q.offer(root.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

Short answer:

the reason is because of a logical mistake in your code that causes an infinite loop, you are using the root node instead of the current node being processed from the queue, which leads to continuously adding the same child nodes back to the queue, causing an infinite loop.

explanation:

your code:

while(!q.isEmpty()){ //here we say as long as the queue is not empty keep looping
            List<Integer> level = new ArrayList<>();
            int size = q.size(); 
            for(int i = 0; i < size; i++){
                level.add(q.peek().val);
                q.poll();
                if(root.left != null){
                    q.offer(root.left); //here we add root left
                }
                if(root.right != null){
                    q.offer(root.right); //here we add root right
                }
                //so in result the loop every time will add the root left and right causing an infinite loop
            }
            result.add(level);
        }
        return result;
    }

as you saw in your code even if you fix the infinite loop, it is still logically wrong, why are you checking the root left and right every time instead of setting a pointer that moves across the tree? as a solution you can use current node and that node must change while you walk through the tree.

solution code

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = q.poll(); //here we make current
                level.add(current.val);
                
                if (current.left != null) { //here we check current left
                    q.offer(current.left); 
                }
                if (current.right != null) { //here we check current right
                    q.offer(current.right);
                }
            }
            result.add(level);
        }

        return result;
    }
}

note that this code only fixes your algorithm, but there are better ways to solve this problem and better code styles, check the submissions that people did to learn from them.