List of Depths

Lessons Learned: recursion, tree traversal

Question 7: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (if you have a tree with depth D, you have D linked lists).

Before diving into this question, check out this article discussing level order traversal. This essentially means traversing a tree in order of the different “levels”, or layers.

You may think by looking at the question that we need to traverse by level to create a list of linked lists, but this is actually not needed as long as we know the level we are on. If we pass a level variable at every recursive step, we can even solve this problem by performing a pre-order traversal as follows:

We’re done! This solution can also be solved through a breadth-first search algorithm, and I encourage you all to dive deeper into this alternative solution.