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! :)

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Data structures

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['']