title: DFS and BFS on a Trie in Java
body: <p>I have a Trie which looks like this:</p>
  
  <pre><code>      Root
       /    \
      b      c
     /      / \
    a      a   h
   /      /   / \
  t      t   a   e
            /   /
           t   e
              / \
             r   s
            /     \
           s       e
  </code></pre>
  
  <p>I'm trying to implement a DFS, and BFS. The BFS works fine, using a queue:</p>
  
  <pre><code>public String breadthFirstSearch() {
      //FIFO Queue to hold nodes
      Queue&lt;TrieNode&gt; nodeQueue = new LinkedList&lt;TrieNode&gt;();
  
      //Output array
      ArrayList&lt;Integer&gt; out = new ArrayList&lt;Integer&gt;();
  
      //Start from root
      nodeQueue.add(this.root);
  
      //While queue is not empty
      while (nodeQueue.isEmpty() == false) {
          //Remove and return first queue element
          TrieNode current = nodeQueue.poll();
          //For node's children
          for (int i=0; i&lt;26; i++) {
              //If not null
              if (current.offspring[i] != null) {
                  //Add node to queue
                  nodeQueue.add(current.offspring[i]);
                  //Add node's index (char) to output array
                  out.add(i);                    
              }
          }
      }
      //Return result
      return indexArrayToString(out);
  }
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>b,c,a,a,h,t,t,a,e,t,e,r,s,s,e
  </code></pre>
  
  <p>Now, I'm trying to implement the DFS (same algorithm, but using a stack) however the output isn't correct:</p>
  
  <pre><code>public String depthFirstSearch() {
      //LIFO Stack to hold nodes
      Stack&lt;TrieNode&gt; nodeStack = new Stack&lt;TrieNode&gt;();
  
      //Output array
      ArrayList&lt;Integer&gt; out = new ArrayList&lt;Integer&gt;();
  
      //Start from root
      nodeStack.push(this.root);
  
      //While stack is not empty
      while (nodeStack.isEmpty() == false) {
          //Remove and return first stack element
          TrieNode current = nodeStack.pop();
          //For node's children
          for (int i=0; i&lt;26; i++) {
              //If not null
              if (current.offspring[i] != null) {
                  //Add node to stack
                  nodeStack.push(current.offspring[i]);
                  //Add node's index (char) to output array
                  out.add(i);                    
              }
          }
      }
      //Return result
      return indexArrayToString(out);
  }
  </code></pre>
  
  <p>This gives:</p>
  
  <pre><code>b,c,a,h,a,e,e,r,s,e,s,t,t,a,t
  </code></pre>
  
  <p>When I want it to give:</p>
  
  <pre><code>t,a,b,t,a,t,a,s,r,e,s,e,e,h,c
  </code></pre>
  
  <p>I can't figure out what's going wrong.</p>