Recursively creating a JSON tree, adding only at the deepest level

Question

I want to create a JSON hierarchy structure of unknown objects, so it must be handled recursively.

Here's my function, where angular.element.isEmptyObject() is inherited from jQuery, and angular.copy() is a function that creates a deep copy of the object (I'm using AngularJS).

function recurseTree(tree, newKey, newId) {
 if(angular.element.isEmptyObject(tree)) {
 tree[newKey] = {_id: newId};
 } else {
 for(var key in tree) {
 if(typeof tree[key] == 'object') recurseTree(tree[key], newKey, newId);
 else tree[newKey] = {_id: newId};
 }
 }
 return angular.copy(tree);
}

Now run this:

var testT = {};
console.log(recurseTree(testT, 'a', '1'));
console.log(recurseTree(testT, 'b', '2'));
console.log(recurseTree(testT, 'c', '3'));
console.log(recurseTree(testT, 'd', '4'));
console.log(recurseTree(testT, 'e', '5'));

You'll notice that the first and second ones return as expected:

{ 
 a: { 
 _id: '1',
 b: {
 _id: '2'
 }
 }
}

but the third one is where I run into trouble.

{ 
 a: { 
 _id: '1',
 b: {
 _id: '2',
 c: {
 _id: '3'
 }
 },
 c: {
 _id: '3'
 }
 }
}

What do I need to fix to get the c object appended ONLY as a child of b, rather than also as a child of a? I'm stumped.

Here's a JSFiddle of it in action, check your console for the results. http://jsfiddle.net/winduptoy/Mjq5D/2/

• Jared Farrish: Can you put together a working jsfiddle.net with all of the dependent libraries?
• 371273: Whoops, sorry I forgot one, I added it to the bottom of the question.

Answer 1

Try this:

function recurseTree(tree, newKey, newId) {
 if(angular.element.isEmptyObject(tree)) {
 tree[newKey] = {_id: newId};
 return;
 } 
 var child = null; // find current tree's child
 for(var key in tree) {
 if (key != '_id') {
 child = tree[key]; // found a child
 break;
 }
 }
 if (child) { // recursively process on child
 recurseTree(child, newKey, newId);
 } else { // no child, so just fill the tree
 tree[newKey] = {_id: newId};
 }
}

Test:

var testT = {};
recurseTree(testT, 'a', '1');
console.log(testT); 
recurseTree(testT, 'b', '1');
console.log(testT); 
recurseTree(testT, 'c', '1');
console.log(testT); 
recurseTree(testT, 'd', '1');
console.log(testT); 
recurseTree(testT, 'e', '1');
console.log(testT);

Please be noted that I have not used angular.copy(tree) for the performance's sake. If you don't want to change the tree, copy it before passing it to the function recurseTree. Please try it on jsFiddle.

• 371273: Thank you so much, this is correct. You have also solved another one of my questions. If you will also post this code here, I will accept your answer. stackoverflow.com/questions/14088181/…
• Hui Zheng: You're very welcome, and I answered that question as per your request.

Answer 2

have a try? is it necessary to use for loop ?

for(var key in tree) {
 if(typeof tree[key] == 'object'){ 
 recurseTree(tree[key], newKey, newId);
 break;
 }
 else {
 tree[newKey] = {_id: newId};
 break;
 }
}

• 371273: Adding the breaks in there fixed it, but can you explain how I can do it without the for loop?
• Teifi: @WindUpToy at the situation you posted, new node was always added to the first-child-node at that tree level. so I said it is unnecessary to use for loop.
• 371273: Hui is correct, this isn't exactly right. His code is now the accepted answer.
• Teifi: @HuiZheng, @Wind Up Toy I just find out the logical error, and posted it before a test, if any better answer, accept it.

Answer 3

My solution:

vm.getChilds = function (data, parent_id) {
 return _.filter(data, function (item) {
 return item.parent_id == parent_id;
 });
 };
 vm.getIds = function (arr) {
 var ids = [];
 arr.forEach(function (item) {
 ids.push(item.id);
 });
 return ids;
 };
 vm.updateList = function (data, arr) {
 var ids = vm.getIds(arr);
 var result = [];
 data.forEach(function (item) {
 if (ids.indexOf(item.id) == -1) {
 result.push(item);
 }
 });
 return result;
 };
 vm.getThree = function (data, parent_id) {
 var items = vm.getChilds(data, parent_id);
 if (items.length == 0) return null;
 var tree = [];
 var newData = vm.updateList(data, items);
 items.forEach(function (item) {
 item.sub_departments = vm.getThree(newData, item.id);
 tree.push(item);
 });
 return tree;
 };