Solving "Binary Tree Level Order Traversal" Leet code Question

Leet code Question no: 102

Companies asked this Question:
Company: no of times
Amazon 2
Bloomberg 11
Uber 2
Apple 2
LinkedIn 25
Microsoft 13
Facebook 12
Oracle 7
Google 5
ServiceNow 3
Splunk 2
Adobe 2
Docusign 2
Accolite 2
TikTok 2

Intuition

We aim to perform a level-order traversal of a binary tree, collecting nodes at each level into sublists.

Approach

1. Utilize a queue for level-order traversal, initializing an empty list WrapList to store results.
2. While the queue is not empty, dequeue nodes, collect their values into sublists, and enqueue their children.
3. Add sublists to WrapList as levels are processed and return it as the result.

Complexity

• Time complexity: O(n) - We visit each node once during the traversal.
• Space complexity: O(n) - The space usage grows with the number of nodes due to the queue and the result list.

Code

/**
 * 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) {
        List<List<Integer>> WrapList = new LinkedList<>();

        if(root == null)
            return WrapList;

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

        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<>();

            for(int i = 0 ;  i < levelNum ; i++){
                TreeNode node = queue.poll();
                subList.add(node.val);

                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }

            WrapList.add(subList);
        }

        return WrapList;
    }
}

Happy coding,
shiva