Recursion

Lesson

Instead of going through the tree deeper and deeper like a DFS, you might want to go through all the closer nodes first, and all the distant nodes last. This is called a called a Breadth-First Search or "BFS".

You can't do a BFS using recursion, because recursion always does the same thing over and over again before doing anything else (like "go left"), which means all recursions are DFS.

It turns out you can do a BFS traversal by taking the code for an iterative preorder traversal, and swapping out the stack with a queue. This way you visit closer nodes first and distant nodes last. Here's the code for a BFS:

Often, people like to write a BFS in a slightly different way: they like to make sure they never add None to the queue. This is the same code as above, but you check if the node is None on a different line. Here's the standard code for a BFS:

So far, the BFS code we wrote code goes node-by-node, but sometimes you want to go layer-by-layer (say you want to find the sum at each layer of a tree). If you want to go layer-by-layer, you can add an inner while loop that goes over the current layer all together. You can use the length of the queue to do this, because the length tells you how many nodes are in the current layer. Here's the code for a layer-by-layer BFS:

You should be comfortable writing these two BFS code segments, node-by-node and layer-by-layer, since they show up a lot.

Time Complexity The amount of time this takes depends on what you fill in for "do something", but if you do somthing simple like printing out the value, this is $O(n)$, since you're visiting all $n$ nodes in the tree.

Space Complexity The queue eventually contains all the nodes in the largest layer of the tree. Assuming you're not storing anything extra in each iteration, this is $O(n)$, even for balanced trees.

Mark as Completed: