• 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
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Tree Traversal - Storing the Path

 
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Friends, its me again....back with another problem.

I am trying to write a method which goes through my tree, finds the element given to the function and gives back the path (nodes) I traversed while I was searching for that element/ object.

My Idea was to work with a few helper-methods to solve the problem.



1. Write a method to check if there is a path from each child of my current node.(There is always only one child-node option that works at each level)




2. If there is a path I want to save the node and check the same thing for the child. I don't care about the nodes that don't have a path.

My questions now:

- Is there a smooth way to store the my paths? Thought about an ArrayList where I add the [i] that leads to the correct path.
- Does my pathExist function work? To be honest I am not even sure if i get the correct result that I want...

Hope this is not to vague and someone can maybe give me a Tip or send me a link to check a concept?
I only find Binary-Tree solutions.

Thank you very much in advance.
 
Marshal
Posts: 71730
312
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you asking how to traverse your tree or only how to record the nodes visited? If you are visiting the nodes recursively, one way to do that is to pass a List<Node> as an argument and add each Node visited to the List after the recursive call. It may be easier to add the nodes to a Stack implementation before the recursive call. Both those suggestions will show the leaf node first and the root last.
 
Bartender
Posts: 4272
160
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I envisage something like:

Not tested!
 
Michael Grünau
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is correct.

My Helper-Method looks like this atm.



Should I implement a List<Node> as an argument inside the helper-Method?
 
Piet Souris
Bartender
Posts: 4272
160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, if Nodes are clear enough to know what path they represent. You could also have a List<Integer> in wich the indices of a Child are stored. Whatever is most clear.
 
Piet Souris
Bartender
Posts: 4272
160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was just looking to see if we can fill that list from the end to the start, removing the need for a boolean result. The fact that the List is not empty is itself proof of the existence of a Path.

But then I saw this line of code:

How do you start this method? It is an instance method, but in order to find the full path, you should invoke: root.findPath, or else get a partial path.
 
Michael Grünau
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So the complete task for the Method was to find the Object in my tree, track the path and build the name via the tracked path.

Below is my complete approach:

 
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you meant this
to be
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic