Just for playing a bit with streams and functional programming, I assigned myself a programming task: given a Tree structure, perform a depth-first and a breadth first traversal of the structure.
This is the code I wrote:
Obviously, the relevant parts of this code are getTraversalDepthFirst and getTraversalBreadthFirst methods. I want to return the list of the nodes of the tree I have to visit, in the order given by the specific traversal strategy.
Now, while getTraversalDepthFirst method implementation seems elegant (at least, for me !), I cannot say the same for getTraversalBreadthFirst , because of that distinct() method I had to use to prune duplicates, i.e nodes that I visited more than once.
I wonder if there is a way to avoid "cheating" by pruning duplicates. I guess that the answer is no, because with BFS I'm forcing a visited order that is not immediately recursive, and I have to put visited nodes in a stack or in a list I populate during traversal, like the following code:
I'd love to hear your thoughts about... and what you think about my solutions to this problem.
I was thinking about a generic-tree structure where each node can have n children. Honestly, after your reply I searched on Wikipedia, and the most similar structure I've found is a k-ary tree, with at most k descendant for each node.
Tree class I posted is not an example to imitate; I should have implemented a Tree class and a TreeNode class, but ultimately the focus of the question is not on the data structure presented.. so I thing we can close an eye without loosing generality.
The only way to perform a level-order traversal properly is to enqueue the nodes that you still need to traverse. To do this, you need to write a custom spliterator that manipulates the queue of nodes that need to be traversed:
It's not pretty, but it does the job cleanly and efficiently.