Logical recursion

Question

trying to write a boolean method that says someone is a member of someone ... but seems to be unable to do this. Of course, an object is a descendant if it is a child ... or a descendant of a child.

public boolean isDescendant(member x){ if (children.contains(x)){ return true; } else{ return false; } } 

but where and how do I insert:

 for (int i = 0; i < children.size(); i++){ isDescendant(children.get(i)); } 

thanks!

Answer 1

Walking trees very slowly down (from root to leaves). Consider this implementation for checking is-ancestor:

 /** * Checks whether the given node is an ancestor of this node. */ public boolean isDescendantOf(Node ancestor) { Preconditions.checkNotNull(ancestor, "Ancestor"); if (equals(ancestor)) { // every node is an ancestor to itself return true; } else if (parent == null) { // not related return false; } else { // recursive call return parent.isDescendantOf(ancestor); } } 

Another way is now a piece of cake.

 public boolean isDescendant(Node descendant) { return descendant.isDescendantOf(this); } 

No cycles, without any effort.

PS:
In my example, I suggest renaming isDescendant to isAncestorOf .

Answer 2

I think you want below:

 // Cleaned up version public boolean isDescendant(member x){ // check for direct descendance if (children.contains(x)){ return true; } // check for being descendant of the children for (Child c: children){ if (children.get(i).isDescendant(x)) { return true; } } return false; } 

Answer 3

 public boolean isDescendant(member currentRoot, member x){ //check the current level if (currentRoot.children().contains(x)){ return true; } //leaf if( currentRoot.children().isEmpty() ){ return false; } //try all my children boolean found = false; for( Member child : currentRoot.children() ){ found = isDescendant( child, x ); if( found ) break; } return found; } 

Most likely you need to rewrite the current root.

Answer 4

Edit: If your data structure has parent pointers, use them instead of looking for your descendants in the tree. If not, consider adding them. See Response from whiskeysierra for a solution with parent pointers. Only if you cannot add them, consider this answer.

---

In the current answer, everyone has two loops through children (one in children.contains() , one later).

This option may be a little more efficient (but it does not change the O-class), and a little shorter. (If children are a set with quick check-content (like a HashSet), and often the hierarchy is not so deep (so you don't need to recursively at all), other answers are better.)

 public boolean isDescendant(Member x) { for(Member child : children) { if(child.equals(x) || child.isDescendant(x)) return true; } return false; } 

If a node is considered a descendant of itself, you can write it as follows:

 public boolean isDescendant(Member x) { if(equals(x)) return true; for(Member child : children) { if(child.isDescendant(x)) return true; } return false; }