title: Retrieve Kth lexicographically smallest string from trie tree
body: <p>I am currently trying to solve a problem which involves retreiving kth lexicographically smallest string from a trie. </p>
  
  <p>Example: let us consider the following set of strings: {"a", "b", "c", "aa", "aab", "ab", "ac", "aac"}. Next, lets say that I am required to find 3rd smallest string from the set. In that case, the result should be "aab". </p>
  
  <p>I am using trie based implementation for the same because the set of strings can be very large and there can be many queries asking to find kth smallest strings from the set. </p>
  
  <p>My trie structure is as follows:</p>
  
  <pre><code>class TrieNode {
  
      char value;  // character stored at the node
      HashMap&lt;Character, TrieNode&gt; children;  // list of all children
      boolean isLeaf; // boolean to check if node has no children
      int count; // number of strings inserted below the current node
  
  }
  </code></pre>
  
  <p>While inserting strings in my trie, I increment the <code>count</code> variable for a trienode every time it is encountered during insertion.</p>
  
  <p>Now, my task is to retrieve kth lexicographically smallest string from the trie. In order to achieve that, I use the following function:</p>
  
  <pre><code>public String findKth(int k) {
      int current_rank = 0;
      String result = "";  // this will be the kth smallest string
      char c = 'a';  // temporary variable to crawl trie in order (a to z)
      HashMap&lt;Character, TrieNode&gt; child = root.getChildren(); // root is the root node of my trie
      while (current_rank &lt; k) {
          if (child.containsKey(c)) { // look at this node
              if(child.get(c).count + current_rank &lt; k) { // look at siblings
                  current_rank += child.get(c).count;
                  c = (char) ((int)c + 1);
              } else { // follow the subtree of this node
                  result += c;
                  child = child.get(c).getChildren();
                  c = 'a';
              }
          } else { // search for next character in order (a-z)
              c = (char) ((int)c + 1);
          }
      }
      return result;
  }
  </code></pre>
  
  <p>However, I am not able to generate result. Sometimes, my program is stuck in infinite loop or it gives incorrect results. What am I missing?</p>