JavaScript: Solving an algorithmic problem

Question

Today I was working on a problem, which states as follows:

Problem:

INPUT: [{..}, {..}, ..] Array of objects;
Each object is has {"id": required, "children": []}
The objects has parent-child relation based on "id" and "children" props
OUTPUT: [{..}, {..}, ..] Array in a tree (hierarchy) order :multi-level.

Input:

[{
    "id": 1,
    "name": "Earth",
    "children": [2, 3]
}, {
    "id": 2,
    "name": "Asia",
    "children": []
}, {
    "id": 3,
    "name": "Europe",
    "children": [4]
}, {
    "id": 4,
    "name": "Germany",
    "children": [5]
}, {
    "id": 5,
    "name": "Hamburg",
    "children": []
}]

OutPut

[{
    "id": 1,
    "name": "Earth",
    "children": [{
        "id": 2,
        "name": "Asia",
        "children": []
    }, {
        "id": 3,
        "name": "Europe",
        "children": [{
            "id": 4,
            "name": "Germany",
            "children": [{
                "id": 5,
                "name": "Hamburg",
                "children": []
            }]
        }]
    }]
}]

My approach

I decided to solve this by iterating through each element in the array and recursively find and append objects to children of each element.

So just to start with, I decided to have only First level children appended their respective parents. And my code is following.

var posts = [{"id":1,"name":"Earth","children":[2,3]},{"id":2,"name":"Asia","children":[]},{"id":3,"name":"Europe","children":[4]},{"id":4,"name":"Germany","children":[5]},{"id":5,"name":"Hamburg","children":[]}]

function getElementById (id, posts) {
	for(var i =0; i< posts.length; i++){
		if(posts[i].id === id){
			var found = posts[i];
///// FUN here -> ////	posts.splice(i, 1);
			return found;
		}
	}
} 

function refactorChildren(element, posts) {
  if(!element.children || element.children.length === 0) {
    return element;
  }
  
  var children = [];
  for(var i = 0; i < element.children.length; i++){
    var childElement = getElementById(element.children[i], posts);    
    children.push(childElement);
  }
  element.children = children;
  
  return element;
}

function iterate(posts) {
  var newPosts = [];
  var des = [...posts]
  for(var i = 0; i < des.length; i++){
    var childedElement = refactorChildren(des[i], des);
     newPosts.push(childedElement);
  }
  
  return newPosts;
}


var filtered = iterate(posts);
console.log(JSON.stringify(filtered))

Surprisingly above code Solves the ACTUAL PROBLEM (except a lil bit of more work)

My Expected Result should be the following: Array of objects with only First level children

[{
    "id": 1,
    "name": "Earth",
    "children": [{
        "id": 2,
        "name": "Asia",
        "children": []
    }, {
        "id": 3,
        "name": "Europe",
        "children": [4]
    }]
}, {
    "id": 4,
    "name": "Germany",
    "children": [{
        "id": 5,
        "name": "Hamburg",
        "children": []
    }]
}]

And I do get the above result if I uncomment the ///// FUN here -> //// line. Which is erasing the iterating object on the go.

So my problem is

I want to know - HOW DID? All the objects got appended correctly to their respective Parent objects by that code? My next step was to add a recursion call to the function refactorChildren(with-childElement).

AND

How did, just by adding posts.splice(i, 1); got me MY expected result from the code?

Please help me understand, I just cant go ahead without knowing "HOW".

Thanks

This doesnt work if a child is in the array before its parent. — Jonas Wilms
– Jonas Wilms, Commented Mar 9, 2019 at 17:24
@Jonas I just tried, it still works works jsfiddle.net/t3gy14zu notice the "Earth" it has its child and its child has its child — Siddhartha Chowdhury
– Siddhartha Chowdhury, Commented Mar 9, 2019 at 17:33
I'm not sure I understand the problem. You wrote the code but don't understand it? What part confuses you exactly? — user10957435
– user10957435, Commented Mar 9, 2019 at 17:36

Jonas Wilms · Accepted Answer · 2019-03-09 17:30:51Z

1

While traversing the objects, you recursively call a function on all its chilfren and remove the objects from the array:

 [
   { id: 1, children: [2], }, // < iterator
   { id: 2, children: [] }, // < gets spliced out recursively
 ]

If a child is in the array before its parent however, this won't work as you copy the child into another array before the parent gets visited.

answered Mar 9, 2019 at 17:30

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Siddhartha Chowdhury Over a year ago

Sorry but I think its not the case I tried putting child before the parent in this example jsfiddle.net/t3gy14zu but it still works somehow!

Abhishek Over a year ago

@SiddharthaChowdhury Once you put 'Asia' before the 'Earth' you can see the difference.

Siddhartha Chowdhury Over a year ago

Guys I only care about the values in "Earth". Whose value is still the same no matter how you change the order. I am not concerned about the order or rest of the indexes. My problem is something else - I wanted to know how the multilevel append happening without recursion.

Nina Scholz · Accepted Answer · 2019-03-09 18:20:06Z

1

Maybe you are interested in a different approach with only a single loop for getting the parent elements and their children.

This works for unsorted data, too.

var data = [{ id: 1, name: "Earth", children: [2, 3] }, { id: 2, name: "Asia", children: [] }, { id: 3, name: "Europe", children: [4] }, { id: 4, name: "Germany", children: [5] }, { id: 5, name: "Hamburg", children: [] }],
    tree = function (array) {
        var r = {},
            children = new Set,
            result = [];

        array.forEach(o => {
            Object.assign(
                r[o.id] = r[o.id] || {},
                o,
                { children: o.children.map(id => (children.add(id), r[id] = r[id] || {})) }
            );
        });
        return Object.values(r).filter(({ id }) => !children.has(id));
    }(data);

console.log(tree);

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

edited Mar 9, 2019 at 18:20

answered Mar 9, 2019 at 17:59

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

1 Comment

Siddhartha Chowdhury Over a year ago

Thank you for another solution, [+1] I have solved the above problem, your code is simpler. But I just wanted to know how is the above happening

Collectives™ on Stack Overflow

JavaScript: Solving an algorithmic problem

Problem:

Input:

OutPut

My approach

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem:

Input:

OutPut

My approach

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related