• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding a Tree Node  RSS feed

 
Jeff Storey
Ranch Hand
Posts: 230
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi. I have an object tree that I'm trying to search for a specific component and I'm having some difficulty with the recursion. My basic code structure is:



The problem is that this returns null when I go down one branch of the tree that does not have a matching node. I want to be able to call:


When I currently call it, it is null unless the first tree branch contains my correct node (it eventually does find the correct node, but the first return of the method is null). Can someone help me modify this so it correctly searches the entire tree and the first return is the correct node?

Thanks,
Jeff
 
Dave Wingate
Ranch Hand
Posts: 262
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can suggest two changes to get you started:


[ May 08, 2007: Message edited by: Dave Wingate ]
 
Jeff Storey
Ranch Hand
Posts: 230
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dave,

Thanks for the response. I'm not clear on how this will solve the problem...the second find method will still return when it hits a branch that doesn't contain my node unless I do a full traversal of the tree to get all the nodes first...

Thanks,
Jeff
 
David McCombs
Ranch Hand
Posts: 212
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The first thing to do is understand why null is being returned if the correct node is not the first node.

Do a simple stack trace and trace through your code. And not just to the point where the node is found. When the node is found the return value does not go back to the original method call that started the recursion.

lets say that the node found is the third node.

A. Enters the tree, node is not found. Call itself.

B. Moves to second node, is not the correct node, calls itself.

C. Moves to the third node is the correct node, passes the reference to B.

B finishes executing, returns null to A

A finishes executing, returns null to the method that first called this recursive method.

Hopefully this will make the solution clear.
 
Dave Wingate
Ranch Hand
Posts: 262
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's some extra detail for tree BFS strategy:

 
Sandeep Deb
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


- Sandeep
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!