This week's book giveaway is in the Python forum.
We're giving away four copies of Python Continuous Integration and Delivery and have Moritz Lenz on-line!
See this thread for details.
Win a copy of Python Continuous Integration and Delivery this week in the Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Devaka Cooray
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Tim Holloway
  • Claude Moore
  • Stephan van Hulst
Bartenders:
  • Winston Gutkowski
  • Carey Brown
  • Frits Walraven

Depth-first and Breadth-first traversal of a tree structure with Streams.  RSS feed

 
Saloon Keeper
Posts: 1110
36
IBM DB2 Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Marshal
Posts: 63314
205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What sort of tree is that? I am not used to seeing Lists in trees.
 
Claude Moore
Saloon Keeper
Posts: 1110
36
IBM DB2 Java Netbeans IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 9799
197
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Claude Moore
Saloon Keeper
Posts: 1110
36
IBM DB2 Java Netbeans IDE Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Simply beautiful.
 
Won't you be my neighbor? - Fred Rogers. tiny ad:
Become a Java guru with IntelliJ IDEA
https://www.jetbrains.com/idea/
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!