Can someone provide guidance on effectively implementing this JavaScript (TypeScript) Tree Recursion function?

Question

Can someone provide guidance on effectively implementing this JavaScript (TypeScript) Tree Recursion function?

I'm currently grappling with coding a recursive function, specifically one that involves "Tree Recursion". I could really use some guidance to steer me in the right direction.

To better explain my dilemma, let's consider a basic example showcasing the data and my objective. Please note that the actual data is significantly more complex...

Essentially, I begin with an array containing a single array of objects as shown below, where the prop2 in any object can either be a valid string or an empty string...

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

The task at hand for my algorithm is to examine the above array, iterate over the objects, and once it encounters an object with an empty string in prop2, it must duplicate the array three times. Subsequently, it should replace the empty string in only that specific object with three different values (one/two/three) like so...

[
    [
        { 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: "" }
    ]
]

Following this modification, the algorithm restarts afresh with the new array consisting of three arrays.

During the subsequent iteration, each of the three arrays will be replicated thrice and the empty string will undergo a similar replacement process.

In this simple instance, the end outcome would be an array comprising nine arrays.

If the original array contained more objects with empty prop2 values, additional iterations would be necessary.

Fundamentally, I am transforming an array of objects with certain props being empty strings by broadly "expanding" those particular prop values to encompass every possible permutation of "one"/"two"/"three".

Although recursion seems ideally suited for this problem, I am encountering challenges when trying to formulate the code.

It appears that the "base case" would entail having an array of objects wherein none possess properties with empty strings – returning said array in such scenarios.

However, I am uncertain about how the other case should be structured beyond invoking the same function thrice with the newly generated variants. The desired output for this alternate scenario also remains unclear to me.

Unfortunately, I have not been able to locate relevant examples resembling the task at hand online.

EDIT: Upon reviewing the responses suggesting recursive solutions, while they indeed function accurately, it is now apparent that arriving at a recursive solution has proven far from straightforward. Surprisingly, the non-recursive approach emerges as the most effective solution.

javascript typescript recursion

Answer 1

Answer №1

Here is a unique solution that can help meet your desired outcome:

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>

Answer 2

Here is a unique solution that can help meet your desired outcome:

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>

Answer 3

Answer №2

Indeed, recursion is the key to achieving this task. The fundamental concept is to update the array and then inspect if further modifications are necessary; if so, recursively call the function with the updated array.

Below is a practical example:

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

function modifyArray(arr) {
  const modified = 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 = modified.some(v => v.some(o => !o[propToCheck]))
  if (notDone) {
    return modifyArray(modified);
  }
  return modified;
}

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

console.log(result);

Answer 4

Indeed, recursion is the key to achieving this task. The fundamental concept is to update the array and then inspect if further modifications are necessary; if so, recursively call the function with the updated array.

Below is a practical example:

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

function modifyArray(arr) {
  const modified = 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 = modified.some(v => v.some(o => !o[propToCheck]))
  if (notDone) {
    return modifyArray(modified);
  }
  return modified;
}

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

console.log(result);

Answer 5

Answer №3

When faced with a problem that may not be naturally approached using recursion, an alternative solution involving a general function can prove effective. This particular function accepts substitutions and a key for identifying empty strings as arguments, leveraging ES6+ syntax and 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)

The approach involves iterating through the array, adjusting the index only when an object with the specified key as an empty string is found. When necessary, replacements are made, and the function recurses on the same index. The termination condition occurs when the key to check is not an empty string and the current index is the last one in the input array.

I'll leave the TypeScript implementation up to you as it's more about typing the input data rather than solving the primary issue at hand.

Answer 6

When faced with a problem that may not be naturally approached using recursion, an alternative solution involving a general function can prove effective. This particular function accepts substitutions and a key for identifying empty strings as arguments, leveraging ES6+ syntax and 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)

The approach involves iterating through the array, adjusting the index only when an object with the specified key as an empty string is found. When necessary, replacements are made, and the function recurses on the same index. The termination condition occurs when the key to check is not an empty string and the current index is the last one in the input array.

I'll leave the TypeScript implementation up to you as it's more about typing the input data rather than solving the primary issue at hand.

Can someone provide guidance on effectively implementing this JavaScript (TypeScript) Tree Recursion function?

Answer №1

Answer №2

Answer №3

Similar questions

When utilizing a custom hook that incorporates useContext, the updater function may fail to update as

Different types of AES256 variants

ways to incorporate searching within JSON data using AJAX and jQuery in JavaScript

What is the best way to iterate through only the selected checkboxes to calculate their

Integrating dynamic transition effects using Jquery Mobile for <div> elements

Transforming an HTML file into a Vue.js component

A long error occurred while using the payloadaction feature of the Redux Toolkit

Add the specified HTML tag to the existing document. An error has occurred: HierarchyRequestError - The action would result in an invalid node

`Animate your divs with slide in and slide out effects using

Execute operations on element itself rather than the output of document.getElementbyId

Updating a Nested Form to Modify an Object

Preserve the wpColorPicker selection using personalized knockout bindings

Tips for simulating a Ref

Struggling to make comparisons with numerical data from MongoDB in an ExpressJS route

Guide on incorporating JSON information into an HTML table

Each time the button is clicked, the settings and values will rotate, creating a new

Extract specific index from a JSON array

Can we enhance the efficiency of this equation?

Unable to group the array based on the key value using Jquery or Javascript

Using Vue.js for instant field validation when sending PHP post forms for enhanced user experience