Implement a function which 
creates a **[radix tree](https://en.wikipedia.org/wiki/Radix_tree)** (a space-optimized trie [prefix tree]) 
in which each node that is the only child is merged with its parent [unless a word from the input ends there]) 
from a given list of words 
using dictionaries (aka hash maps or hash tables) where:

1. The dictionary keys are the nodes.
2. Leaf nodes are empty dictionaries.
3. The value for empty input is an empty dictionary.
4. Words are all lowercase or empty strings.
5. Words can contain duplicates.

### Examples:

```python
>>> radix_tree()
{}

>>> radix_tree("")
{}

>>> radix_tree("", "")
{}

>>> radix_tree("radix", "tree")
{"radix": {}, "tree": {}}

>>> radix_tree("ape", "apple")
{"ap": {"e": {}, "ple": {}}}

>>> radix_tree("apple", "applet", "apple", "ape")
{"ap": {"ple": {"t": {}}, "e": {}}}

>>> radix_tree("romane", "romanus", "romulus", "rubens", "rubicon", "rubicundus")
{"r": {"om": {"an": {"e": {}, "us": {}}, "ulus": {}},
       "ub": {"ens": {}, "ic": {"on": {}, "undus": {}}}}}

>>> radix_tree("appleabcd", "apple")
{"apple": {"abcd": {}}}
```

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:
def radix_tree(*words):
	

Solutions:
from itertools import groupby
from operator import itemgetter
from os.path import commonprefix
first = itemgetter(0)

def radix_tree(*words):
	words = [w for w in words if w]
	result = {}
	for (key, grp) in groupby(sorted(words), key=first):
		lst = list(grp)
		prefix = commonprefix(lst)
		result[prefix] = radix_tree(*(w[len(prefix):] for w in lst))
	return result


def radix_tree(*words):
	byFirstChar = {}
	for w in words:
		if w != '':
			l = byFirstChar.get(w[0], [])
			l.append(w[1:])
			byFirstChar[w[0]] = l
	result = {}
	for (c, l) in byFirstChar.items():
		rt = radix_tree(*l)
		if len(rt) == 1 and (not '' in l):
			for (key, value) in rt.items():
				c = c + key
				rt = value
		result[c] = rt
	return result


from itertools import groupby

def radix_tree(*d, need=1):
	if not {i for i in d if i}:
		return {}
	store = {}
	for (i, j) in groupby(sorted(d) if need else d, lambda x: x[0]):
		words = list(j)
		if len(words) == 1:
			store[words[0]] = {}
		else:
			common = next((j for (j, i) in enumerate(zip(*words)) if len(set(i)) != 1), len(min(words, key=len)))
			store[words[0][:common]] = radix_tree(*[i[common:] for i in words if i[common:]], need=0)
	return store


from os.path import commonprefix

def radix_tree(*words):
	groups = {}
	for word in words:
		if word:
			groups[word[0]] = groups.get(word[0], []) + [word]
	root = {}
	for group in groups.values():
		prefix = commonprefix(group)
		root[prefix] = radix_tree(*(w[len(prefix):] for w in group))
	return root


def radix_tree(*W):
	D = {}
	for w in W:
		if w:
			D[w[0]] = D.get(w[0], []) + [w[1:]]
	Z = {}
	for k in D:
		T = radix_tree(*D[k])
		if len(T) == 1 and '' not in D[k]:
			for j in T:
				(k, T) = (k + j, T[j])
		Z[k] = T
	return Z


def radix_tree(*a):
	r = {}
	for s in a:
		d = r
		for x in s + '*':
			if x not in d:
				d[x] = {}
			d = d[x]

	def g(d):
		dd = {}
		for x in d:
			d[x] = g(d[x])
			if len(d[x]) == 1:
				(k, v) = [*d[x].items()][0]
				dd[x + k] = v
			else:
				dd[x] = d[x]
		return dd

	def h(d):
		dd = {}
		for x in d:
			d[x] = h(d[x])
			if x != '*':
				dd[x if x[-1] != '*' else x[:-1]] = d[x]
		return dd
	return h(g(r))


def radix_tree(*Q):
	(U, R) = (set(Q), {})
	for Q in Q:
		T = R
		for Q in Q:
			if not Q in T:
				T[Q] = {}
			T = T[Q]

	def H(Q, S):
		T = list(Q)
		for V in T:
			if 1 == len(Q[V]) and S + V not in U:
				B = next(iter(Q[V]))
				Q[V + B] = Q[V][B]
				del Q[V]
				T.append(V + B)
			else:
				H(Q[V], S + V)
	H(R, '')
	return R


from itertools import groupby

def radix_tree(*words):
	d = {}
	if not any(words):
		return d
	words = sorted(words)
	for g in (list(g) for (_, g) in groupby(words, key=lambda w: w[0] if w else '')):
		i = next((i for i in range(len(g[0])) if not all((len(w) > i and w[i] == g[0][i] for w in g))), len(g[0]))
		d[g[0][:i]] = radix_tree(*(w[i:] for w in g if len(w) > i))
	return d


from functools import reduce

def splitAlong(xs, ys):
	i = 0
	try:
		while xs[i] == ys[i]:
			i += 1
	except IndexError:
		pass
	return (xs[:i], xs[i:], ys[i:])

def insert(tree, word):
	for (key, val) in tree.items():
		(pref, wt, kt) = splitAlong(word, key)
		if pref:
			if kt:
				del tree[key]
				tree[pref] = {wt: {}, kt: val} if wt else {kt: val}
			else:
				insert(tree[pref], wt)
			return tree
	if word:
		tree[word] = {}
	return tree

def radix_tree(*words):
	return reduce(insert, words, {})