Java: Binary Tree Level Order Traversal

Thought Process

To traverse a binary tree level by level, we can do Breadth-First Search (BFS) traversal of the tree. We start by adding the root node to the queue. At each step, we determine the number of nodes at the current level, which is equal to the queue's size before processing begins. Then, we process each node one by one by removing it from the queue, storing its value in a temporary list, and adding its children (if any) to the queue for the next level. This process repeats until the queue is empty, ensuring that nodes are visited level by level in an efficient manner. 

/**
 * 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>> ans = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();

        if(root == null)
            return ans;

        qu.offer(root);
        while(!qu.isEmpty()){

            int szOfQueue = qu.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<szOfQueue;i++){

                TreeNode nod = qu.poll();
                if(nod.left != null)
                    qu.offer(nod.left);
                
                if(nod.right != null)
                    qu.offer(nod.right);

                list.add(nod.val);
            }
            ans.add(list);
        }
        return ans;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the queue depends on the maximum number of nodes at any level. In the worst case, the space complexity is O(n).

Code copied!