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

💡 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