How do you do a level order traversal of a binary tree?
You use a queue. You put the root in the queue, and then you take the nodes out one at a time and put their children at the back of the queue.
from collections import deque
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
queue = deque([root])
output = []
while queue:
node = queue.popleft()
output.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return output
So how does it work? A queue is first in, first out, so the nodes come out in the order that you put them in. And you put the children of each node in as you go, so the tree is walked from the top down, and from the left to the right inside each level.
the tree 8
/ \
3 10
/ \ \
1 6 14
the queue
[8] take 8, add 3 and 10
[3, 10] take 3, add 1 and 6
[1, 6, 10] take 1
the result is 8, 3, 10, 1, 6, 14
And it is different from the three depth first walks in one important way. Those ones go all the way down and all the way back up before they move on. This one finishes a whole level before it starts the next one.
And the complexity is O of n for the time, because every node is put into the queue once and taken out once, and O of w for the space, where w is the width of the widest level.
So the rule to remember is this. A queue gives you the level order, and the children go in at the back.
The next two questions in this topic show the shape of the answer and the version without a queue.