Building an index of items from an iterable-of-tuples
Don't use make variables scoped to a function 'private'.
They're 'protected' so please, just remove the _ from them.

If we look at your next block.
You use iter_tup.__next__().
Don't.
Use next!
If you see __{name}__ then you should always check if there is a better way.
And so I'd use:

first = next(iterator, None)
if first is None:
    return {}


The next block to get the length and to rebuild the iterator is fine.

The reduce is fine, I dislike how static it is.
And so if I were to write this function I'd change it.
But it's fine.

I'd change _add_tup_to_idx to just a plain for loop.
Sure it means you mutate something, oh well.
It's much easier to read and understand.
I'd change it to:

dictionary = idx_ctor()
for tup in iter_all:
    reduce(_getitem, tup[:-1], dictionary).append(tup[-1])
return dictionary


Finally I'll go over a few more 'high-level' things. It's much easier to read if you use good variable names.
Take for example:

def build_index(iterator):
    iterator = iter(iterator)
    first = next(iterator)
    if first is None:
        return {}
    depth = len(first) - 1
    iterator = chain([first], iterator)

    ddict = reduce(lambda d, _: partial(defaultdict, d),
                   repeat(None, depth),
                   list)
    dictionary = ddict()
    for item in iterator:
        reduce(getitem, item[:-1], dictionary).append(item[-1])
    return dictionary


Now you seem to put emphasis on it being a hash-tree.
But what do you get if you do:

build_index((('a',), ('b',), ('c',)))


Is it a dictionary, or is it a list?
Now what do you get if you enter these:

build_index((('a', 'b'), ('b', 'c'), ('c', 'd')))
build_index(())


Yes the they return different types.
The above two are dictionary's, and the first is a list.
That is a massive edge case.

I think the design should be based around an infinite default dict.
And for it to always return a dict.
And so you could use the following recursive function:

def ddict():
    return defaultdict(ddict)


Now we just have to change your for loop.
If we slice the string into two at the second to last position,
and remove the item from the list if the second is empty:

dictionary = ddict()
for head, tail in ((i[:-2], i[-2:]) for i in iterable):
    if not tail:
        continue


Now before you say, that's not functional!
Yeah it's half functional, well the comprehension is.
It's easier to read this way, as if Python were a functional based language it'd be more like:

iterable
    .map(i =&gt; (i[:-2], i[-2:]))
    .filter(i =&gt; i[1])


Now we could do that, but it'd be icky, take:

(i for i in ((i[:-2], i[-2:]) for i in iterable) if i[0])
filter(lambda i: i[0], map(lambda i: (i[:-2], i[-2:]), iterable))


And so they all are the same, so just go for the most readable.

For the last bit, we will do what you were doing before.
But with two changes.
To allow for tail to have a length of one, we need to use extend rather than append.
and to get a list you'll have to use setdefault with a list.

This gives a quite functional function:

def build_index(iterable):
    def ddict():
        return defaultdict(ddict)
    dictionary = ddict()
    for head, tail in ((i[:-2], i[-2:]) for i in iterable):
        if not tail:
            continue
        (reduce(getitem, head, dictionary)
            .setdefault(tail[0], [])
            .extend(tail[1:]))
    return dictionary


You can also change getitem to a function that uses setdefault to remove the need for defaultdict and getitem.