Javascript deriving a Tree from a set of URLs

Question

Guys am trying to create a dynamic menu list. There is no limit to the depth of elements that can be created by a user.

MY PROBLEM

My set of URL looks like this

var json_data = [
    {
        "title" : "Food",
        "path" : "/root",
    },
    {
        "title" : "Cloths",
        "path" : "/root",
    },
    {
        "title" : "Veg",
        "path" : "/root/Food",
    },
    {
        "title" : "Brinjal",
        "path" : "/root/Food/Veg",
    },
    {
        "title" : "T shirt",
        "path" : "/root/Cloths",
    },
    {
        "title" : "Shirt",
        "path" : "/root/Cloths",
    },
    {
        "title" : "Green brinjal",
        "path" : "/root/Food/Veg/Brinjal",
    }
];

I want the titles to be in a hierarchy format which I eventually will render in form of ul > li to create the menu - in front-end.

The Hierarchy should be something like this:

[
  {
    "title": "Food",
    "path": "/root",
    "children": [
      {
        "title": "Veg",
        "path": "/root/Food",
        "children": [
          {
            "title": "Brinjal",
            "path": "/root/Food/Veg",
            "children": [
              {
                "title": "Green brinjal",
                "path": "/root/Food/Veg/Brinjal",
                "children": []
              }
            ]
          }
        ]
      }
    ]
  },
  {
    "title": "Cloths",
    "path": "/root",
    "children": [
      {
        "title": "T shirt",
        "path": "/root/Cloths",
        "children": []
      },
      {
        "title": "Shirt",
        "path": "/root/Cloths",
        "children": []
      }
    ]
  }
]

WHAT I TRIED

    // Add an item node in the tree, at the right position
    function addToTree( node, treeNodes ) {
        // Check if the item node should inserted in a subnode
        for ( var i=0; i<treeNodes.length; i++ ) {
            var treeNode = treeNodes[i];
            // "/store/travel".indexOf( '/store/' )
            if ( node.path.indexOf( treeNode.path + '/' ) == 0 ) {
                addToTree( node, treeNode.children );
                // Item node was added, we can quit
                return;
            }
        }
        // Item node was not added to a subnode, so it's a sibling of these treeNodes
        treeNodes.push({
            title: node.title,
            path: node.path,
            children: []
        });
    }
    //Create the item tree starting from menuItems
    function createTree( nodes ){
        var tree = [];

        for ( var i=0; i<nodes.length; i++ ) {
            var node = nodes[i];
            addToTree( node, tree );
        }
        return tree;
    }

// variable = "json_data" is the set of URLS
var menuItemsTree = createTree( json_data );
console.log(menuItemsTree)

And the result it yields is this:

[
  {
    "title": "Food",
    "path": "/root",
    "children": [
      {
        "title": "Veg",
        "path": "/root/Food",
        "children": [
          {
            "title": "Brinjal",
            "path": "/root/Food/Veg",
            "children": [
              {
                "title": "Green brinjal",
                "path": "/root/Food/Veg/Brinjal",
                "children": []
              }
            ]
          }
        ]
      },
      {
        "title": "T shirt",
        "path": "/root/Cloths",
        "children": []
      },
      {
        "title": "Shirt",
        "path": "/root/Cloths",
        "children": []
      }
    ]
  },
  {
    "title": "Cloths",
    "path": "/root",
    "children": []
  }
]

The elements "T Shirt" and "Shirt" is pushed inside the Food's children:[] which those should be inside Cloth's children:[]

The solution I have used is taken from Here

I trying to derive an algorithm myself- but its not clicked exactly right yet. Please help if any one already has a solution. In case if I can derive a solution myself, I will share it here. above code is Thanks

Answer 1

Below is the logic. here is a Working Fiddle

var json_data = [{
  "title": "Food",
  "path": "/root",
}, {
  "title": "Cloths",
  "path": "/root",
}, {
  "title": "Veg",
  "path": "/root/Food",
}, {
  "title": "Brinjal",
  "path": "/root/Food/Veg",
}, {
  "title": "T shirt",
  "path": "/root/Cloths",
}, {
  "title": "Shirt",
  "path": "/root/Cloths",
}, {
  "title": "Green brinjal",
  "path": "/root/Food/Veg/Brinjal",
},{
  "title": "Test cloth",
  "path": "/root/Cloths/Shirt",
}];


// Add an item node in the tree, at the right position
function addToTree(node, treeNodes) {
  var parentNode = GetTheParentNodeChildArray(node.path, treeNodes) || treeNodes;

  parentNode.push({
    title: node.title,
    path: node.path,
    children: []
  });
}

function GetTheParentNodeChildArray(path, treeNodes) {
  for (var i = 0; i < treeNodes.length; i++) {
    var treeNode = treeNodes[i];

    if (path === (treeNode.path + '/' + treeNode.title)) {
      return treeNode.children;
    } 
    else if (treeNode.children.length > 0) {
      var possibleParent = false;

      treeNode.children.forEach(function(item) {
        if (path.indexOf(item.path + '/' + item.title) == 0) {
          possibleParent = true;
          return false;
        }
      });

      if (possibleParent) {
        return GetTheParentNodeChildArray(path, treeNode.children)
      }
    }
  }
}


//Create the item tree starting from menuItems
function createTree(nodes) {
  var tree = [];

  for (var i = 0; i < nodes.length; i++) {
    var node = nodes[i];
    addToTree(node, tree);
  }
  return tree;
}

// variable = "json_data" is the set of URLS
var menuItemsTree = createTree(json_data);
console.log(menuItemsTree);

Limitation of this logic: This logic works if the parent node is parsed before the child nodes, hence it is recommended to sort the list of URLs ( i.e. json_data[] ) likewise. Here's a snippet of Sorting-before + tree-structuring-the-sorted

Hope this is helpful