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

Utilizing ReactStrap: a guide to retrieving the id of the chosen dropDownItem

I keep seeing this strange [object HTMLSpanElement] appearing on my HTML page

The Algolia Hit Component is having difficulty functioning properly within a grid layout

Ensuring input validity and blocking changes if not compliant with AngularJS patterns

Discovering the specific URL of a PHP file while transmitting an Ajax post request in a Wordpress environment

Storing data from a collection of interface objects in a string array

Activating gzip compression using fetch.js

Setting up a CentOs Linux environment to host and run a node.js server

Matching multiline input with RegExp and grouping matches from consecutive lines

Next.js application shows 404 errors when trying to access assets within the public directory

Error encountered when attempting to convert a JSON object to a String using JSON.stringify(), due to a cyclic object value

Angular.js: how to filter an ng-repeat by a missing key/value pair

The C++ Induction Algorithm displays sluggish performance when contrasted with Dynamical Programming techniques

Utilizing query parameters in JavaScript

Angular - enabling scroll position restoration for a singular route

Setting up React Router in a nested directory with a flexible route structure

Is There a Way to Abandon a route and Exit in Express during a single request?

Implementing the jquery mobile data-native-menu feature in a select element dynamically generated from jeditable

Ways to ensure all images have been successfully uploaded to Firebase before executing a function

What measures can be taken to keep the rightmost element from moving when hovered over?