How do I properly implment this JavaScript (TypeScript) Tree Recursion function?

Question

I'm trying to code a recursive function but I'm struggling and I was hoping someone could help push me in the right direction. I believe that this would be considered "Tree Recursion".

This is a trivial example to illustrate the data and what I'm trying to do. Obviously, the real data is more complex...

Basically, I start with an array containing a single array of objects like below where prop2 in any of the objects can either be a valid string or an empty string...

[
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]

My algorithm needs to look at the array above and iterate over the objects. As soon as it encounters an object with an empty string in prop2, it needs to clone the array three times and replace the empty string in that object (and only that object) with three different values (one/two/three) like this...

[
    [
        { prop1: "abc", prop2: "one" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ],
    [
        { prop1: "abc", prop2: "two" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ],
    [
        { prop1: "abc", prop2: "three" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]

Then the algorithm starts again, except that the the input is this new array containing three arrays.

So on the second iteration, each of the three arrays will get cloned three times and the empty string will get replaced in the same way.

The end result for this simple example would be an array of nine arrays.

If the array had more objects with empty prop2 values, there would be more iterations.

Basically, I'm taking an array of objects where some of the props are empty strings and "expanding" that particular prop value to every permutation of "one"/"two"/"three"

I know that this is an ideal problem for recursion but I'm having trouble figuring out the code.

I think that the "base case" would probably be where I have an array of objects and none of the objects have properties with empty strings. That case would return that array.

I don't know what the other case would look like other than calling the same function three times with the three newly created variants. I also don't know what this case should be returning.

I'm having trouble finding reference examples online that are similar to what I'm trying to do.

EDIT: Looking at the recursive responses, even though they all do work, it's obvious that a recursive solution wasn't as straightforward as I thought it would be. The non-recursive answer is actually the best answer.

A.Amayreh · Accepted Answer · 2022-03-06 05:53:26Z

1

I suggest this non-reclusive solution it serves your end-result requirements:

const myTree = [
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
];

let nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
while(nodesWithEmptyStrings.length > 0) {
  nodesWithEmptyStrings.forEach(n => {
    const firstEmptyStringLeaveIndex = n.findIndex(l=> l.prop2==="");
    n[firstEmptyStringLeaveIndex].prop2 = "one";
    const copy1 = JSON.parse(JSON.stringify(n));
    copy1[firstEmptyStringLeaveIndex].prop2 = "two";
    myTree.push(copy1);
    
    const copy2 = JSON.parse(JSON.stringify(n));
    copy2[firstEmptyStringLeaveIndex].prop2 = "three";
    myTree.push(copy2);
  });
  nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
}

document.getElementById('result').innerText = JSON.stringify(myTree, null, 2);

<pre id="result"></pre>

answered Mar 6, 2022 at 5:53

A.Amayreh

1201 silver badge4 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

krick Over a year ago

I found all the responses to my question very informative but this ended up being the cleanest solution to the problem. My initial attempt at a non-recursive solution involved pushing and popping arrays off of a stack and it seemed that a recursive solution would be the simplest but this is much clearer.

Titus · Accepted Answer · 2022-03-06 06:13:35Z

Yes, you can do this using recursion. The basic principle is to modify the array and then check if it needs to be modified some more, if that is the case, return the result of calling the function with the new array.

Here is an example:

const fillers = ['one', 'two', 'three'];
const propToCheck = 'prop2';

function recursion(arr) {
  const mod = arr.reduce((a, c) => {
    const found = c.find(v => !v[propToCheck]);
    if (found) {
      const tmp = c.filter(v => v !== found);
      return [...a, ...fillers.map(filler => [...tmp, { ...found, [propToCheck]: filler }])];
    }
    return [...a, c];
  }, []);
  const notDone = mod.some(v => v.some(o => !o[propToCheck]))
  if (notDone) {
    return recursion(mod);
  }
  return mod;
}

const result = recursion([
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]);

console.log(result);

fast-reflexes · Accepted Answer · 2022-03-06 06:35:25Z

I don't know if this is a problem that intuitively I would want to solve with recursion, but this general function that takes both substitutions and what key to check for the empty string as arguments would work (using es6+ syntax and functionality with a lot of destructuring):

const substitute = (data, index, keyToCheck, substitutes) => {
  const indexOfObjectWithEmptyKeyToCheck = data[index].findIndex(obj => obj[keyToCheck] === "")
    if(indexOfObjectWithEmptyKeyToCheck === -1) {
        if(index === data.length - 1)
            return data
        else
            return substitute(data, index + 1, keyToCheck, substitutes)
    }
    else {
        return substitute(
            [
                ...data.slice(0, index),
                ...(substitutes.map(
                    substitute => [
                        ...data[index].slice(0, indexOfObjectWithEmptyKeyToCheck),
                        { ...data[index][indexOfObjectWithEmptyKeyToCheck], [keyToCheck]: substitute },
                        ...data[index].slice(indexOfObjectWithEmptyKeyToCheck + 1)
                    ]
                )),
                ...data.slice(index + 1)
            ],
            index,
            keyToCheck,
            substitutes
        )
    }
}


const SUBSTITUTES = ["one", "two", "three"];

const result = substitute(
    [
        [
            { prop1: "abc", prop2: "" },
            { prop1: "def", prop2: "one" },
            { prop1: "ghi", prop2: "" }
        ]
    ],
    0, 
    "prop2", 
    SUBSTITUTES
)
console.log(result)
console.log("Size of result: " + result.length)

Basically, we iterate through the array, only incrementing the index if the current array has no object where the key to check is the empty string, otherwise we do replacements as necessary and recurse on the same index. The base case is when the key to check is not the empty string and the index is the last index of the input array.

The Typescript part I left to you as an exercise as I don't believe typing the input data is the big problem here.

Collectives™ on Stack Overflow

How do I properly implment this JavaScript (TypeScript) Tree Recursion function?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related