Skip to content
Advertisement

Recursive iteration over deeply nested object to find parent

I have a data tree structure with children:

JavaScript

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:

JavaScript

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

JavaScript

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

Advertisement

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

JavaScript

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.

JavaScript

and then call it like

JavaScript

to limit the number of searches to 100.

User contributions licensed under: CC BY-SA
4 People found this is helpful
Advertisement