# Building a nested tree structure from an ordered list

I have an ordered list in this format. The data is ordered by path so that the list will never contain a child before the parent in the list.

id, path
1, null
2, null
3, 1
4, 1-3
5, 2
6, 2-5


Each entry contains the path it needs to place itself in the tree structure.

The catch is that the list doesn't always start with nulls sometimes the list starts in the middle of a path.

id, path
10, 2-5-6
11, 2-5-6-10
12, 2-5-6-10
13, 2-5-6-10-11
14, 2-5-6-10-11-13
15, 2-5-6-10-12


In this case I need to treat the first record in this list as the root and build out everything else as normal without permanently editing the paths of any items in the list.

    function nestComments(comments) {
var nested = {
};

var normalize,
path,
level;

for (var i = 0; i < comments.length; i++) {

tree = nested,
isValid = true;

if (comment.path) {
path = comment.path.split('-');

//keep track of the permalink the path

//if the first comment has a path then we need to normalize the path
if (i === 0) {
normalize = path.length;
}

if (normalize) {
//normalize the path based on the peramlink's path
path.splice(0, normalize);
}

for (var j = 0; j < path.length; j++) {
var step = path[j];

var index = tree.Comments.findIndex(x => x.comment_id.toString() === step);
if (index < 0) {
isValid = false;
break;
}

}

}

if (!path || path.length === 0) {
level = 0;
} else {
level = path.findIndex(x => x === path[path.length - 1]);
}

if (!trimComments(level, tree) || !isValid) {
continue;
}

}
return nested;
}

var result;
switch (level) {
case 0:
result = true; // limit based on the sql query
break;
case 1:
break;
case 2:
break;
case 3:
break;
case 4:
break;
case 5:
break;
case 6:
break;
default:
result = false;
break;
}
return result;
}

var comments = nestComments([{comment_id: 4, path:"1-2-3"},{comment_id: 5, path:"1-2-3-4"},{comment_id: 6,path:"1-2-3-4"}, {comment_id: 7, path:"1-2-3-4-6"},{comment_id: 8, path:"1-2-3-4-6"}, {comment_id: 9, path:"1-2-3-4-6-7"}, {comment_id: 10, path:"1-2-3-4-6-7-9"}, {comment_id: 11, path:"1-2-3-4-6-8"}]);

console.log(comments);

• Welcome to Code Review! I hope you get some good answers. – Phrancis Jul 15 '16 at 16:46
• This seems related to another recent question. – 200_success Jul 15 '16 at 17:40

First, nestComments appears very long. Functions that usually do too much are also functions that become harder to test. Also, code that is is visually long is usually hard to understand. Consider splitting it off into smaller, manageable functions.

Now one thing that makes code slow is when you nest loops. In this case, you have 3 levels, 2 for loops and findIndex which is essentially a loop. Nesting loops can cause operations to explode exponentially. What you'd want to do is keep it to a minimum, since some operations really require nested loops.

Next would be trimComments. The problem of having a switch (or any code that does comparison against a hard set of items) is that you have to play catch-up with the things you need to compare. You will constantly dive into code to add things you never wrote in the first place.

Also, your trimComments is just sending in a value and expecting a result that's pretty 1:1, reminiscent of a key-value pair. This can easily be done with regular objects instead of a switch statement. You can find the input from the keys, and get its corresponding value.

Looking for how trimComments is used, I see that you use it to determine if a comment is included. Ok, cool, you use it to skip a push. But the problem is that you've already done processing, then just suddenly skip it from being included. That's a waste of operations. Also, you can preprocess your paths so that you only include the intended maximum number of comment paths, and operate on that instead.

Here's my take on it:

1. Normalize your input by working on full paths.
2. Trim down the paths based on maximums.
3. Operate on the remaining paths.

And the code would be broken down into:

const commentsPerLevel = {
'1': 5
'2': 5
'3': 3
'4': 2
'5': 1
'6': 1
}

function getMaxForLevel(level){
// returns value from commentsPerLevel or a default value
}

// returns full paths from input
return comments.map(comment => 0-${comment.path}-${comment.comment_id});
}

function trimPaths(paths){
// returns paths trimmed based on maximums from commentsPerLevel
}

function buildCommentTree(paths){
// build comment tree based on paths
}