The goal of this kata is to implement [trie](https://en.wikipedia.org/wiki/Trie) (or prefix tree) using dictionaries (aka hash maps or hash tables), where:

1. the dictionary keys are the prefixes
2. the value of a leaf node is `None` in Python, `nil` in Ruby and `null` in Groovy, JavaScript and Java.
3. the value for empty input is `{}` in Python, Ruby, Javascript and Java (empty map) and `[:]` in Groovy.

**Examples:**

```python
>>> build_trie()
{}
>>> build_trie("")
{}
>>> build_trie("trie")
{'t': {'tr': {'tri': {'trie': None}}}}
>>> build_trie("tree")
{'t': {'tr': {'tre': {'tree': None}}}}
>>> build_trie("A","to", "tea", "ted", "ten", "i", "in", "inn")
{'A': None, 't': {'to': None, 'te': {'tea': None, 'ted': None, 'ten': None}}, 'i': {'in': {'inn': None}}}
>>> build_trie("true", "trust")
{'t': {'tr': {'tru': {'true': None, 'trus': {'trust': None}}}}}
```

Happy coding! :)

Difficulty: introductory

Starter code:

def build_trie(*words):
	

Solutions:
def build_trie(*words):
    root = {}
    for word in words:
        branch = root
        length = len(word)
        for i in range(1, length+1):
            length -= 1
            key = word[:i]
            if key not in branch: 
                branch[key] = None
            if length and not branch[key]: 
                branch[key] = {}
            branch = branch[key]
    return root

def build_trie(*words):
    d = {}
    for word in words:
        dd = d
        w, l = "", len(word)
        for c in word:
            w += c
            l -= 1
            if w not in dd: dd[w] = None
            if l and dd[w] is None: dd[w] = {}
            dd = dd[w]
    return d

def build_trie(*words):
    trie = {}
    for word in words:
        node = trie
        l = len(word)
        for i in range(1, l+1):
            w = word[:i]
            node[w] = node = {} if l-i and node.get(w) is None else node.get(w)
    return trie


build_trie = lambda *words: (cheker(words) or {})
    
cheker = lambda wos, i=1: None if not wos else {l: cheker(tuple(x for x in wos if x[:i]==l and x!=l), i+1) for l in set(e[:i] for e in wos if e)}


def build_trie(*words):
    return (cheker(words) or {})
    
def cheker(words, i=1):
    doc, selter = {}, set(e[:i] for e in words if e)
    for fl in selter:
        doc[fl] = cheker(tuple(e for e in words if e[:i]==fl and e!=fl),  i+1) 
    return None if not words else doc


 
def build_trie(*words):
    trie={} 
    k=''
    def recurse(trie,wd,k):
        for l in wd:
            k=k+l
            if k in trie:
                if trie[k]==None and len(wd)>1:
                  trie[k]={}
                recurse(trie[k],wd[1:],k)
            else:
                trie[k]={} if len(wd)>1 else None
                recurse(trie[k],wd[1:],k)
            return trie
    
    [recurse(trie,word,'') for word in words]
     
    return trie





 



def build_trie(*words):
    trie = {}
    for word in words:
        node = trie
        for i in range(1, len(word)+1):
            prefix = word[:i]
            if prefix not in node:
                node[prefix] = None
            if i < len(word) and node[prefix] is None:
                node[prefix] = {}
            node = node[prefix]
    return trie

def build_trie(*words):
    trie = {}
    for word in words:
        trie = insert(trie, build_branch(word) if word else {})
    return trie        

def build_branch(word, i=0):
    if i < len(word):
        return {word[:i+1]: build_branch(word, i+1)}

def insert(trie, branch):
    if branch and trie:
        k, v = next(iter(list(branch.items())))
        if k in trie:
            trie[k] = insert(trie.get(k, {}), v)
        else:
            trie[k] = v
    return trie or branch


from itertools import accumulate


def f(d, word):
    for c in accumulate(word):
        if c not in d:
            d[c] = {}
        d = d[c]


def replace(d):
    return {key: replace(value) for key, value in d.items()} if d else None


def build_trie(*words):
    d = {}
    for word in words:
        f(d, word)
    return replace(d) or {}

def build_trie(*Q) :
    R = {'' : {}}
    for V in Q :
        for B in range(len(V)) :
            B = V[:1 + B]
            if not B in R :
                if not R[B[:-1]] : R[B[:-2]][B[:-1]] = R[B[:-1]] = {}
                R[B[:-1]][B] = R[B] = None
    return R['']