Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • 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
  • Jeanne Boyarsky
  • Bear Bibeault
  • Knute Snortum
  • Liutauras Vilda
Sheriffs:
  • Tim Cooke
  • Devaka Cooray
  • Paul Clapham
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Ron McLeod
  • Ganesh Patekar
  • salvin francis
Bartenders:
  • Tim Holloway
  • Carey Brown
  • Stephan van Hulst

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

 
Ranch Foreman
Posts: 1065
24
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: 62231
193
  • 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
Ranch Foreman
Posts: 1065
24
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.
 
Bartender
Posts: 9558
189
  • 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
Ranch Foreman
Posts: 1065
24
IBM DB2 Java Netbeans IDE Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Simply beautiful.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!