Building a nested tree structure from an ordered list

Question

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 = {
        "Comments": []
    };
    if (!comments) return nested;

    var normalize,
        path,
        level;
        
    for (var i = 0; i < comments.length; i++) {

        var comment = comments[i],
            tree = nested,
            isValid = true;

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

            //permalinked comments don't have null paths
            //keep track of the permalink the path
            //adjust children paths to treat permalink path like the root

            //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;
                }
                tree = tree.Comments[index];

                tree.Comments = tree.Comments || [];
            }

        }

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

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

        tree.Comments.push(comment);

    }
    return nested;
}


function trimComments(level, tree) {
    var result;
    switch (level) {
        case 0:
            result = true; // limit based on the sql query
            break;
        case 1:
            result = tree.Comments.length < 5;
            break;
        case 2:
            result = tree.Comments.length < 5;
            break;
        case 3:
            result = tree.Comments.length < 3;
            break;
        case 4:
            result = tree.Comments.length < 2;
            break;
        case 5:
            result = tree.Comments.length < 1;
            break;
        case 6:
            result = tree.Comments.length < 1;
            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);

Please help me improve this code.

Answer 1

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
  return commentsPerLevel[level] || 0;
}

function getCommentPaths(comments){
  // 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
}

function nestComments(comments){
  const paths        = getCommentPaths(comments);
  const trimmedPaths = trimPaths(paths);
  const commentTree  = buildCommentTree(trimmedPaths);
  return commentTree;
}

I left out implementation for some, but the idea is to break down your operations into functions so they won't be that hard to maintain.