Questions about Iterative Deepening Depth First search in java

Question

I'm looking at the pseudocode on Wikipedia for this and trying to use it to write the algorithm in java. My question comes in a difference in how the result is returned. On wikipedia, one result is returned, and this breaks out of the search. In mine, everytime a relevant node is found, it is added to a list, and that list is to be returned when the tree has been processed. How would I detect the end of the tree in order to break out and return the list?

Wikipedia:

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return null
}

Mine:

    public List<String> dfid(Tree t, String goal)
    {
        List<String> results = new ArrayList<String>();
        String result;

        int depth = 0;
        while (true) //obviously not the way to go here
        {
            result = dls(t.root, goal, depth);
            if (result.contains(goal))
                results.add(result);
            depth += 1;
        }
        return results; //unreachable return
    }

    public String dls(Node node, String goal, int depth)
    {
        if (depth == 0 && node.data.contains(goal))
        {
            return node.data;
        }
        else if (depth > 0)
        {
            for(Node child : node.children)
            {
                dls(child, goal, depth-1);
            }
        }
        return null;
    }

Edit: After changes:

//depth first iterative deepening
        //control variables for these methods
        boolean maxDepth = false;
    List<String> results = new ArrayList<String>();

    public List<String> dfid(Tree t, String goal)
    {
        int depth = 0;

        while (!maxDepth)
        {
            maxDepth = true;
            dls(t.root, goal, depth);
            depth += 1;
        }
        return results;
    }

    public void dls(Node node, String goal, int depth)
    {
        if (depth == 0 && node.data.contains(goal))
        {
            //set maxDepth to false if the node has children
            maxDepth = maxDepth && children.isEmpty();
            results.add(node.data);
        }
        for(Node child : node.children)
        {
            dls(child, goal, depth-1);
        }
    }

Answer 1

I think you can accomplish this with a boolean maxDepth = false instance variable. On each iteration of your while loop, if maxDepth == true then exit, else set maxDepth = true. In dls when you reach depth == 0 then set maxDepth = maxDepth && children.isEmpty(), i.e. set maxDepth to false if the node has any children.

Also, change dls to a void method. Replace return node.data with results.add(node.data), where results is an ArrayList or HashSet depending on whether you want to filter out duplicates.

If you always want to visit every node in the tree, then modify dls as follows

public void dls(ArrayList<String> results, Node node, String goal)
{
    if (node.data.contains(goal))
    {
        results.add(node.data);
    }
    for(Node child : node.children)
    {
        dls(child, goal, depth-1);
    }
}