Recursive iteration over deeply nested object to find parent

I have a data tree structure with children:

{  id: 1,
   name: "Dog",
   parent_id: null,
   children: [
         {
             id: 2,
             name: "Food",
             parent_id: 1,
             children: []
         },
         {
             id: 3,
             name: "Water",
             parent_id: 1,
             children: [
                 {
                    id: 4,
                    name: "Bowl",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 5,
                    name: "Oxygen",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 6,
                    name: "Hydrogen",
                    parent_id: 3,
                    children: []
                 }
             ]
         }
   ]
}

Any child data object can have more children as shown in the above data. This represents a DOM structure that a user could select an item from to add a child to.

I have a known text title of the selected item from the DOM as well as the data the user wants to insert. I am having trouble finding a recursive algorithm that will allow me to add the new data to the correct level of the tree.

Here is a list of me thinking through the problem and trying to pseudo code it:

inputs:

1. tree (data from above)
2. parentTitle from clicked item in DOM

outputs:

1. tree with item inserted

steps:

1. determine highest used id to know what next unique id is
2. check current level of data for match with the title of parent
3. if matched then set id and parent_id in new data and push into children of parent
4. if no match then check if current level data have children
5. if current level has children needs to repeat steps 2+ for each until match is found

Here is my code:

function askUserForNewItem(e) {
   const tree = getTree(); // returns above tree data structure
   const name = prompt( 'Enter new item’s name:' ); // user input to match and insert as new item in tree
   const clickedTitle = getClickedTitle(e); // returns string title of clicked on item from DOM - for example "Dog" or "Bowl"
   const parent = determineParent(tree, clickedTitle);
   const parent_id = parent[0].id;
   // TODO - needs to set real unique id (highest unused id)
   const newId = 101; // hard coded for now, needs to be dynamic
   // TODO - needs to insert into correct level of children array in tree
   return tree.children.push({ id: newId, name, emoji, children: [], parent_id: parent_id });
}

function determineParent(tree, clickedTitle) {

    if(tree.children.length === 0) {
        return false;
    }
    let treeLevel = tree;
    let parent = [];
    while(treeLevel.children.length !== 0) {
        parent = treeLevel.children.filter(child => child.name === clickedTitle);
        if(parent.length !== 0) {
            break;
        }
        else {
            // what to do here to make this recursive?
        }
    }

    return parent;
}

So if a user typed “Cat” while clicking the add button for “Dog” then a new object

{
    id: 7,
    name: "Cat",
    parent_id: 1,
    children: []
}

Would be inserted into children of the first level “Dog” object in the data tree.

Answer

If you want a recursive solution, you should modify the determineParent method so it searches down the tree. Not sure this is exactly what you are searching for, but i hope you get the general idea

function determineParent(curNode, clickedTitle) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    // not found yet, do a recusive search down the tree.

    for(const node of curNode.children) {
        return determineParent(node,clickedTitle);
    }

    return null; // not found.
}

the idea is to start at the topmost node (curNode) and first determine if it is the correct parent, if not then take the first children see if it matches and if not search down it’s children and so on.

When dealing with recursion it may be necessary to handle the situation where you may experience circular references, consider a scenario where a node has a child that points to the nodes parent or grandparent, the recursive method will run forever (in real life it will run out of stack space and throw an exception).

One way it so include a safeguard counter that is decreased on each recursive call, and then bail out when it reaches zero.

function determineParent(curNode, clickedTitle, safeGuard) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    if(safeGuard===0)
        return null; // bail out 

    // not found yet, do a recusive search down the tree.
    for(const node of curNode.children) {
        return determineParent(node,clickedTitle,--safeGuard);
    }

    return null; // not found.
}

and then call it like

  this.determineParent(tree,"title",100);

to limit the number of searches to 100.