# Is there a solution to the following thought experiment / problem involving trees?

I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.

Basically I have a tree with $$n$$ nodes, each of which is assigned a numeric label $$l\in\{0,\ldots,k\}$$, $$k\in\mathbb{Z}, k\geq0$$. More than one node can have the same label. An example of such a tree is shown below.

Please excuse me for the poor quality of my drawing.

My aim is to find a mapping $$m$$ of the labels $$\{0,\ldots,k\}$$ to the set $$s\in\{A,\ldots,Z\}$$ (i.e., from numbers to letters) such that each path from a root node to a leaf node becomes a human-readable English word.

In the example above, a possible mapping could be $$1\to S, 2\to E, 3\to L, 4\to A, 5\to N, 6\to W, 7\to D$$, yielding the following resulting tree:

As you can see, each path from the root node to a leaf node produces an intelligible English word, which is from left to right $$SEA, SELL, SAW$$ and $$SAND$$.

Having a complete English dictionary at our disposal with all possible letter combinations that form intelligible English words, how could one find such a mapping $$m:=l\to s$$, assuming that any tree given as input is mappable?

EDIT: Any mapping needs to map different numbers to different letters, i.e., be injective.

• Does a mapping need to map different numbers to different letters? In other words, should it be injective? May 30 at 19:41
• @Nathaniel Yes, thank you for your comment. I have amended the question. May 30 at 20:11
• Just as a comment, if you build a trie out of the dictionary, then you almost have a labelled subtree isomorphism problem. It's "almost" because the root of the "pattern" needs to be one level from the root of the "text" tree, and the leaves also need to match. May 31 at 1:43

What you're trying to build is kind of a crossword. This link shows an algorithm that generates crosswords. It's not quite your case, but it's close enough. Basically the algorithm does this (starting from the first word $$w$$ of the ordered dictonary):

1. If $$w$$ can be placed in a path and if it hasn't already been placed in every path possible: insert it. Else, we'll call $$w$$ the next avaible word and start again.
2. Search for a word $$w_1$$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 1. and insert $$w$$ in another path
3. Search for a word $$w_2$$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 2. and insert $$w_1$$ in another path
4. [...]

This is a backtracking algorithm.

I would suggest to sort all the words alphabetically and then by length (you'll have something like $$a, aa, ab, b, ba, bb, c, ccc,\ [...]$$). I think an example will clarify why.

Let's say you just inserted $$SEA$$ in your example. To fill the path $$1-4-6$$ you'll have to search words that start with $$SA$$. This can be done easly with the sort. Starting from words with length $$3$$ wich start with $$S$$: if you encounter $$S\_\$$, where $$\_\$$ can be every letter other then $$A$$, or a word with length $$>3$$ then $$SEA$$ can't be placed in that specific path.

To be more specific, let's say this is a portion of the ordered list of words: $$[...], RAW, SAA, SAW, SEA, [...]$$. Then we can be sure that if the path $$1-4-6$$ can be fulfilled by a word, it needs to be after $$RAW$$ and before $$SEA$$.

For an implementation you could perhaps use a list of lists like this one: $$[[1, 2, 4], [1, 2, 3, 3], [1, 4, 6],\ ...]$$. Whenever you place a word in a path you replace every number of the list with the corrisponding letter: $$[[S, E, A], [S, E, 3, 3], [S, A, 6],\ ...]$$