In the following code, I have a function extractWords which given a simple trie data structure should return a list of words.

I am currently using a recursion (even another way is acceptable) to try to get the words. The '*': null, reppresents the end of the word in the trie.

Current result is ["ble"], which is wrong, I would like to have instead ["ble", "bout"].

I am not able to move to the next path in the tree. Could you please point me out in the right direction? Thanks

TS Play Ground

type Word = string;
type Words = Word[];

type TriNode = {
  [key: string]: TriNode | null;
};

let currentNode: TriNode = {
        '*': null,
        b: {
          l: {
            e: {
              '*': null,
            },
          },
          o: {
            u: {
              t: {
                '*': null,
              },
            },
          },
        },
      };

const extractWords = (triNode: TriNode): Words => {
  const recursion = (triNode: TriNode, currentWord: Word): Words => {
    const keys = Object.keys(triNode);
    let results: Words = [];
    for (let i = 0; i < keys.length;) {
      const key = keys[i];
      if (key === '*') {
        results.push(currentWord);
        i  ;
      } else {
        const x = triNode[key];
        if (x) {
          i  ;
          return recursion(x, currentWord   key);
        }
      }
    }
    return results;
  };

  return recursion(triNode, '');
};


if (currentNode) {
  const r = extractWords(currentNode);
  console.log(r); // current result ["ble"], I would like to have instead ["ble", "bout"]
}

CodePudding user response：

The problem is that after the recursive call returns your code performs a return and does not allow the surrounding loop to make more iterations.

So replace the following statement:

      return recursion(x, currentWord   key);

with:

      results.push(...recursion(x, currentWord   key));

Note that the results will also include "", as you have a * key at the top level.

Other remarks

• It is a bit odd that you increment the loop variable in the loop body, and not in the for heading as is usually done.
• You could use a for..in loop.
• This is a nice candidate for a generator function.

That would look like this:

let currentNode = {'*': null,b: {l: {e: {'*': null,},},o: {u: {t: {'*': null,},},},},};

const extractWords = (triNode) => {
  function* recursion(triNode, currentWord) {
    for (const key in triNode) {
      if (key === '*') {
        yield currentWord;
      } else {
        const x = triNode[key];
        if (x) {
          yield* recursion(x, currentWord   key);
        }
      }
    }
  };

  return Array.from(recursion(triNode, ''));
};


if (currentNode) {
  const r = extractWords(currentNode);
  console.log(r);
}