# Binary Tree Level Order Traversal

Oct 12th, 2021
854
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from collections import deque
2.
3. # Definition for a binary tree node.
4. # class TreeNode:
5. #     def __init__(self, val=0, left=None, right=None):
6. #         self.val = val
7. #         self.left = left
8. #         self.right = right
9. class Solution:
10.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
11.         # Handle empty root case
12.         if not root:
13.             return []
14.
15.         result = []
16.
18.         q = deque([(root, 0)])
19.
20.         # Keep track of previous node length to track when we reach a new depth
21.         prevnode_depth = -1
22.
23.         # Store values in current level
24.         level_values = []
25.
26.         while len(q) > 0:
27.             currnode_tuple = q.popleft()
28.             currnode = currnode_tuple[0]
29.             currnode_depth = currnode_tuple[1]
30.
31.             # If level_values is empty, add currnode
32.             if len(level_values) == 0:
33.                 level_values.append(currnode.val)
34.
35.             # Else if the currnode is at same level, add currnode val to level_values
36.             elif currnode_depth == prevnode_depth:
37.                 level_values.append(currnode.val)
38.
39.             # Else if currnode is not at the same level
40.             else:
41.                 # Add level values to result
42.                 result.append(level_values)
43.                 # Reset level values
44.                 level_values = [currnode.val]
45.
46.             # Append currnode's children to BFS
47.             if currnode.left:
48.                 q.append((currnode.left, currnode_depth + 1))
49.             if currnode.right:
50.                 q.append((currnode.right, currnode_depth + 1))
51.
52.             prevnode_depth = currnode_depth
53.
54.         # Return result array
55.         result.append(level_values)
56.         return result