Reverse Breadth First traversal in C#

Question

Anyone has a ready implementation of the Reverse Breadth First traversal algorithm in C#?

By Reverse Breadth First traversal , I mean instead of searching a tree starting from a common node, I want to search the tree from the bottom and gradually converged to a common node.

Let's see the below figure, this is the output of a Breadth First traversal :

In my reverse breadth first traversal , 9,10,11 and 12 will be the first few nodes found ( the order of them are not important as they are all first order). 5, 6, 7 and 8 are the second few nodes found, and so on. 1 would be the last node found.

Any ideas or pointers?

Edit: Change "Breadth First Search" to "Breadth First traversal" to clarify the question

Answer 1

Use a combination of a stack and queue.

Do the 'normal' BFS using the queue (which I presume you know to do already), and keep pushing nodes on the stack as you encounter them.

Once done with the BFS, the stack will contain the reverse BFS order.

Answer 2

Anyone has a ready implementation of the Reverse Breadth First traversal algorithm in C#?

How can we answer that question when you provide so little information? You didn’t give us any information on how your graph/tree is implemented and there’s no standardized interface for graph traversal, hence no standardized algorithms.

Unless you’re using a big graph library (which will already include your algorithm, or close enough!) there won’t be a ready-made algorithm that fits your exact data structure.

Furthermore, implementing BFS is trivial, and so is reverse BFS. It will be faster for you to implement it than searching for an existing implementation that fits your data structure.

Answer 3

Run a normal BFS from rootNode and let depth[i] = linked list of nodes with depth i. So for your example you'll have:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. You can build this with a simple BFS search. Then print all the nodes in depth[maxDepth], then those in depth[maxDepth - 1] etc.

The depth of a node i is equal to the depth of its father node + 1. The depth of the root node can be considered 1 or 0.