title: Python - printing out a trie in alphabetically sorted order with a recursive function
body: <p>I'm working my way through the <a href="https://www.nltk.org/book/ch04.html#exercises" rel="nofollow noreferrer" title="NLTK book">NLTK book</a> by Bird, Klein, and Loper and I'm stuck on a problem.  I'm working through the book for my own personal enrichment, and not for a class.</p>
  
  <p>The problem I'm stuck on is 4.29:</p>
  
  <p><em><strong>Write a recursive function that pretty prints a trie in alphabetically sorted order, e.g.:</strong></em></p>
  
  <p><code>chair: 'flesh'
  ---t: 'cat'
  --ic: 'stylish'
  ---en: 'dog'</code></p>
  
  <p>I'm using this code from the book to create the trie:</p>
  
  <pre><code>def insert(trie, key, value):
      if key:
          first, rest = key[0], key[1:]
          if first not in trie:
              trie[first] = {}
          insert(trie[first], rest, value)
      else:
          trie['value'] = value
  
  trie = {}
  insert(trie, 'chat', 'cat')
  insert(trie, 'chien', 'dog')
  insert(trie, 'chair', 'flesh')
  insert(trie, 'chic', 'stylish')
  
  </code></pre>
  
  <p>I modified an answer from <a href="https://stackoverflow.com/a/36977856/9097207">this discussion</a> for a function that recursively goes through the trie and pulls out the complete keys and values:</p>
  
  <pre><code>def trawl_trie(trie):
      unsorted = []
      for key, value in trie.items():
          if 'value' not in key:
              for item in trawl_trie(trie[key]):
                  unsorted.append(key + item)
          else:
              unsorted.append(': ' + value)
  
      return unsorted
  </code></pre>
  
  <p>But I'm not able to use recursion to make an alphabetical list, nor can I figure out how to use recursion to replace the duplicate parts of the keys.  The best that I can do is to create a helper function that goes through the results of the function above:</p>
  
  <pre><code>def print_trie(trie):
  
      # sort list alphabetically
      alphabetized = list(sorted(set(trawl_trie(trie))))
  
  
      print(alphabetized[0])
  
      # compare the 2nd item ~ to the previous one in the list.
      for k in range(1, len(alphabetized)):
          # separate words from value
          prev_w, prev_d = (re.findall(r'(\w+):', alphabetized[k - 1]), re.findall(r': (\w+)', alphabetized[k - 1]))
          curr_w, curr_d = (re.findall(r'(\w+):', alphabetized[k]), re.findall(r': (\w+)', alphabetized[k]))
          word = ''
  
          # find parts that match and replace them with dashes
          for i in range(min(len(prev_w[0]), len(curr_w[0]))):
              if prev_w[0][i] == curr_w[0][i]:
                  word += prev_w[0][i]
  
          curr_w[0] = re.sub(word, '-' * len(word), curr_w[0])
          print(curr_w[0] + ": " + str(curr_d[0]))
  </code></pre>
  
  <p>This would be the output:</p>
  
  <pre><code>print_trie(trie)
  
  chair: flesh
  ---t: cat
  --ic: stylish
  ---en: dog
  
  </code></pre>
  
  <p>Does anyone know if it would be possible to get the same result with one recursive function?  Or I am stuck using a recursive function to go through the trie, and a second helper function to make everything look nice?</p>
  
  <p>Cheers,</p>
  
  <ul>
  <li>MC</li>
  </ul>