Searching for a node in a tree in Java

Question

I have a binary tree made with the following constructor:

public Person(String name, int age, char gender, Person c1, Person c2)

where c1 is the left child and c2 is the right child.

I want to write a method that searches for a particular name within a maximum generation. So like a.depthFirstSearch(Eva, 1); where Eva is the name to search for and 1 is the maximum number of generations (or levels) I can look into.

Here's what I have: EDIT:

public Person depthFirstSearch(String name, int maxGeneration)
{
    {
Person temp;
if (maxGeneration>1){
    if (this.name.equals(name)){
        temp=this;
        return temp;
        }
    else{
    if (child1!=null)
        temp=child1.depthFirstSearch(name, maxGeneration-1);
    if (child2!=null)
        temp=child1.depthFirstSearch(name, maxGeneration-1);
    }
}   
return null;
}
}

There's two problems here. I think depth gets reset to 0 every time the function calls itself, so I know I can either keep track of depth somewhere else or find an alternative. The other problem, I think, is that child2 is never really reached, since I return at child1. I'm not really sure how this works so if someone could explain that, that'd be great. Any suggestions for some fixes?

Also, I'm told that I have to search depth first, meaning looking into the deeper generations first. I'm not really sure what that means and how different it is from the logic I'm using in my implementation.

casablanca · Accepted Answer · 2010-11-07 02:41:10Z

Since you decrement maxGeneration in each recursive call, you don't need the depth variable at all: when maxGeneration == 0 you simply don't search any more and return null.

As for your other problem, instead of directly returning the value of child1.depthFirstSearch(...), store the value in a temporary variable. If it is not null, you have found the node, so return it immediately, otherwise continue searching under child2.

Update:

It should be if (maxGeneration >= 1) ... (greater than or equal to), otherwise the last call with maxGeneration == 1 will always return null. Alternatively, you can just check for 0 and return null:

if (maxGeneration == 0)
  return null;

// rest of your code

Also, you still aren't using the return value to check if the node was actually found in the left subtree or not. Right now, even if you find the node under child1, you still look under child2 and you will end up returning null, which is wrong. You need to search under child2 only if the left search returned null:

Person temp;
if (child1 != null) {
  temp = child1.depthFirstSearch(name, maxGeneration-1);
  if (temp != null)
    return temp; // found the node, just return
}
// otherwise the following code will execute
if (child2 != null) {
  temp = child2.depthFirstSearch(name, maxGeneration-1);
  if (temp != null)
    return temp; // found the node, just return
}
// didn't find node under either child
return null;

Thanks a lot. This worked. But now explain something to me. Why do we, after checking temp!=null, return it right away? When we have temp = child1.depthFirstSearch(name, maxGeneration-1);, do we run the recursion first or do we advance to the next line that checks (temp!=null)`? I'm not understanding how this works..
@fprime: The code runs in exactly the same order you put it. So yes, the recursive call runs first, then if it returned something not null, it means we found the node, so we return it. Otherwise, we continue searching under child2.

Collectives™ on Stack Overflow

Searching for a node in a tree in Java

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related