Algorithm to find a "recursive" item in a Javascript data structure

Question

Say I have a Javascript data structure such as:

var data = {
	id: '5551212',
 children: [
 	{id: '5551213'},
 {id: '5551214'},
 {
 id: '5551215',
 children: [
 	{id: '5551213'},
 {id: '5551212'}		// <--- I want to detect THIS one! It's a recursive entry.
 // or a similar occurrence anywhere in the tree.
 ]}
 ]
};

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

I'm looking for a general algorithm to detect a "recursive" item such as the one shown. I find that it's easy enough if the recursive item is just below the "parent" but what if the duplication can occur anywhere?

In this case these are mechanical assembly part numbers. So while it's no problem creating a data structure like this, actually building a recursive assembly is impossible. So I need to find a potential mistake on the user's part before they try to build something impossible.

When searching for algorithms, all I'm getting are recursive programming examples and discussions or here on StackOverflow most questions seem to be about how to create such a recursive structure.

I'm working in Javascript w/ JQuery but I'm looking for an applicable algorithm here, not necessarily an implementation.

• guest271314: Have you tried using JSON.stringify()? What should occur if the value is found?
• Pointy: @guest271314 I don't think the question is about objects with cycles. I think it's about finding property values that have been re-used in a way that violates some contract.
• Anthony: I think you mean "recurring" or "duplicate" not recursive. Recursive would be if you had a value for one of the members of the object set to the parent object.
• guest271314: @Pointy Yes, JSON.stringify() replacer function is recursive and can be used to match or remove properties from the resulting JavaScript object remove object from nested array. RegExp could also be used to match duplicate values. It is not clear what should occur if duplicate property, value pairs occur.
• kabanus: Is a violating id any id referencing an ancestor? i.e. the grand-grand child of root is the father of the child of root along the same branch?

Answer 1

How to do it:

1. Check if parents of the current subtree contain its root id
2. If no, and subtree has children - check their subtrees recursively
3. If there are no children - return false

And here is the code:

function isRecursive(tree, parents){
 if (parents.indexOf(tree.id) !== -1){
 return true;
 } else if (tree.children) {
 return tree.children.some(child => isRecursive(child, [tree.id].concat(parents)));
 }
 return false;
}
isRecursive(data, []);

It can be improved by replacing array with set but I wanted to make it as compatible as possible.

• georg: This won't work if there are duplicates in parallel branches, e.g. children: [{id:X},{id:X}]
• jwh20: @georg, for my purposes at least, duplicates in parallel branches is OK. That's an acceptable construct. I'm only interested in duplicates where a child of the same id as any of its ancestors.

Answer 2

Use this:

var arr = []
function detectRecursive(object){
 var x
 for(x in object){
 if(arr.indexOf([x,object[x]])==-1){
 arr.push([x,object[x]])
 var tmp = {} 
 if(typeof object[x] == typeof tmp){
 detectRecursive(object[x])
 }
 }
 }
}

This loops over the keys and values of the array

• Pointy: ?? The object in the OP can be successfully stringified as JSON.
• Pointy: Try it! The question is not about actual cycles in the data structure, but about property values that violate some constraint.
• jwh20: I tried the JSON.stringify suggestion but there is nothing "illegal" about this data structure. It stringified just fine

Answer 3

You could use a Map to keep track of the "path" keyed by each id value. Then when you find an id is already in that Map, you could push this pair of paths to a results array.

Here is how that would work:

function collectDuplicates(data) {
 const map = new Map,
 dups = [];
 function recurse(data, path) {
 if (map.has(data.id)) {
 dups.push([data.id, map.get(data.id), path]);
 } else {
 map.set(data.id, path);
 }
 (data.children || []).forEach( (child, i) => {
 recurse(data.children[i], path + '.children[' + i + ']');
 })
 }
 recurse(data, 'data');
 return dups;
}
// Sample
var data = {
	id: '5551212',
 children: [
 {id: '5551213'},
 {id: '5551214'},
 {
 id: '5551215',
 children: [
 {id: '5551213'},
 {id: '5551212'}
 ]
 }
 ]
};
console.log(collectDuplicates(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }

In this snippet I built the path in a notation that corresponds to the object notation to get to the two objects that have the same id property, but you could of course use a completely different notation or reference system.