title: Questions about Iterative Deepening Depth First search in java
body: <p>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?</p>
  
  <p>Wikipedia:</p>
  
  <pre><code>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 &gt; 0)
      for each child in expand(node)
        DLS(child, goal, depth-1)
    else
      return null
  }
  </code></pre>
  
  <p>Mine: </p>
  
  <pre><code>    public List&lt;String&gt; dfid(Tree t, String goal)
      {
          List&lt;String&gt; results = new ArrayList&lt;String&gt;();
          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 &amp;&amp; node.data.contains(goal))
          {
              return node.data;
          }
          else if (depth &gt; 0)
          {
              for(Node child : node.children)
              {
                  dls(child, goal, depth-1);
              }
          }
          return null;
      }
  </code></pre>
  
  <p>Edit: After changes:</p>
  
  <pre><code>//depth first iterative deepening
          //control variables for these methods
          boolean maxDepth = false;
      List&lt;String&gt; results = new ArrayList&lt;String&gt;();
  
      public List&lt;String&gt; 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 &amp;&amp; node.data.contains(goal))
          {
              //set maxDepth to false if the node has children
              maxDepth = maxDepth &amp;&amp; children.isEmpty();
              results.add(node.data);
          }
          for(Node child : node.children)
          {
              dls(child, goal, depth-1);
          }
      }
  </code></pre>