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:
![](https://substackcdn.com/image/fetch/w_1456,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2F8d18ad2f-9722-4629-af20-792156600c8c_1332x788.png)
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.