Binary Tree Level Order Traversal Leetcode

raVaN-DEV — Thu, 02 Jan 2025 18:00:10 +0000

Problem Statement - 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: []

Binary Tree Level Order Traversal Python Solution

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

Coding Pattern Used in this Solution

The coding pattern used in all the provided implementations is Tree Breadth-First Search (BFS).
This pattern commonly traverses a tree level by level, processing all nodes at the current depth before moving to the next depth.
BFS is implemented using a queue data structure to keep track of nodes at each level.

Time and Space Complexity for this Solution

The Time complexity is O(N) because each node is visited once.
The Space complexity is O(M) because the queue (or recursion stack) holds up to the maximum number of nodes at any level.

Happy Reading :)

DEV Community: raVaN-DEV

Binary Tree Level Order Traversal Leetcode

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

Binary Tree Level Order Traversal Python Solution

Coding Pattern Used in this Solution

Time and Space Complexity for this Solution