0102. Level Order Traversal

Medium | Tree + Traversal | 20 ms (99.85%), 14.6 MB (69.19%)

❓ Problem Statement

Source: LeetCode - Binary Tree Level Order Traversal GitHub: Solution / Performance

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).

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

💡 Ideas

Instead of using Stack, for level-order, we need to use Queue.

Since level-order traversal starts from left to right, the left-most node will be the one pushed at first. On the other hand, the right-most node will be the one pushed at last.

Traversing from left to right means we need to pop nodes in a FIFO method, so Queue is exactly the data structure we need.

🤖 Python3

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [[root.val]]
        
        # ===================================================
        #  Binary Tree + Level Order Traversal (Iterative)  =
        # ===================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [root]
        
        while stack:
            tmp = []
            for i in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                
                if node.left: stack.append(node.left)
                if node.right: stack.append(node.right)
                    
            ans.append(tmp)
                    
        return ans
        
        '''
        # ===================================================
        #  Binary Tree + Level Order Traversal (Recursive)  =
        # ===================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        
        def recursive(node: TreeNode, depth: int) -> None:
            if len(ans) == depth: ans.append([])
            ans[depth].append(node.val)
            
            if node.left: recursive(node.left, depth + 1)
            if node.right: recursive(node.right, depth + 1)
        
        recursive(root, 0)
        return ans
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        /* base case */
        if(root == null) return new ArrayList<>();
        
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<Integer>();
            int size = queue.size();
            for(int i=0; i<size ; i++) {
                TreeNode node = queue.remove();
                tmp.add(node.val);
                
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            
            result.add(tmp);
        }
        
        return result;
    }
}