Examples / Binary tree BFS▶Run in PyTrace
Level Order Traversal Visualization (Python BFS)
Level order traversal is breadth-first search (BFS) on a tree: visit the root, then all nodes at depth 1, then depth 2, and so on. A queue keeps the nodes waiting to be visited, and processing exactly len(queue) nodes per round separates the levels.
PyTrace draws the binary tree from LeetCode notation ([3,9,20,null,null,15,7]), so you can follow which node is being dequeued while the deque and the result list fill up.
ComplexityO(n) time, O(w) extra space where w is the maximum width of the tree.
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultInputs
root[3,9,20,null,null,15,7]
expected[[3],[9,20],[15,7]]
What to watch
- The binary tree, with the current
nodehighlighted - The
queue(deque) as an array: nodes join at the back and leave from the front resultgetting one new list per level