Algorithm for Transforming Data Structures in Tree Plugin Displays

Published: 2017-06-03

Problem Background

In scenarios that display directory structures, organizational hierarchies, and similar layouts, we often use mature tree plugins for easy presentation, such as zTree. Most plugins support parsing two kinds of data source formats: a common two-dimensional (flat) data structure and a tree (hierarchical) data structure. The naming for these two structures may vary across plugins; here I will refer to them as two-dimensional structure and tree structure. Examples are shown below:

// Two-dimensional data structure
[{
  "id": "001",
  "name": "Headquarters",
  "parentId": "0"
}, {
  "id": "002",
  "name": "Secondary Store 1",
  "parentId": "001"
}, {
  "id": "003",
  "name": "Tertiary Store",
  "parentId": "002"
}, {
  "id": "004",
  "name": "Secondary Store 2",
  "parentId": "001"
}]

// Tree data structure
[{
    "id": "001",
    "name": "Headquarters",
    "parentId": "0",
    "children": [{
      "id": "002",
      "name": "Secondary Store 1",
      "parentId": "001",
      "children": [{
        "id": "003",
        "name": "Tertiary Store",
        "parentId": "002",
        "children": []
      }]
    }, {
      "id": "004",
      "name": "Secondary Store 2",
      "parentId": "001",
      "children": []
    }]
}]

However, in some plugins or special scenarios, we need to convert between these two data structures and must write a helper function to do so. Below I provide two utility functions to perform the conversions.

Note: It should be noted that the utility functions have not been tested with very large data volumes, so if you need real-time or large-scale source data conversion, please test and analyze them yourself and consider preprocessing or asynchronous approaches. Due to limitations in my technical ability, there is room for algorithmic performance optimization; if you have a better approach, please share — thanks!

Solution

I will introduce the conversion algorithms between the two data structures separately. For each section I will first paste the full function code for easy copy-paste, then briefly explain the general logic.

Two-dimensional structure => Tree structure

/**
 * Convert a general two-dimensional data structure into a tree structure
 * @param  {String} rootParentIdValue  Represents the parent id value of root nodes
 * @param  {String} parentIdName       The field name used for the parent id
 * @param  {String} nodeIdName         The field name used as the primary key for each object in the flat structure
 * @param  {Array} listData            The flat-structure data
 * @return {Array}                     The converted tree-structure data
 */
function listToTree(rootParentIdValue, parentIdName, nodeIdName, listData) {
  if (listData instanceof Array && listData.length > 0 && listData[0][parentIdName]) {
    var rootList = [],
        nodeList = []
      
    listData.forEach(function(node, index) {
      if (node[parentIdName] == rootParentIdValue) {
        rootList.push(node);
      } else {
        nodeList.push(node);
      }
    });

    if (nodeList.length > 0 && rootList.length > 0) {
      childrenNodeAdd(rootList, nodeList);
      return rootList;
    } else if (rootList.length > 0) {
      throw new Error("No corresponding child node collection");
    } else {
      throw new Error("No corresponding parent node collection");
    }

    function childrenNodeAdd(rootNodeList, childrenList) {
      if (childrenList.length > 0) { 
        rootNodeList.forEach(function(rootNode) {
          rootNode["children"] = [];
          var childrenNodeList = childrenList.slice(0); 
          childrenList.forEach(function(childrenNode, childrenIndex) {
            if (parentIdName in childrenNode && rootNode[nodeIdName] == childrenNode[parentIdName]) {
              rootNode["children"].push(childrenNode);
              childrenNodeList.splice(childrenIndex, 1);
            }
          });
          childrenNodeAdd(rootNode["children"], childrenNodeList);
        });
      }
    }
    
  } else {
    throw new Error("Incorrect format, cannot convert");
  }
}

This function can be tested by callinglistToTree("0", "parentId", "id", sourceData)to invoke it,sourceDatarefers to the two-dimensional data example given at the start of the article.

Below is a brief explanation of the logic. Line 10 does a basic validation of the input parameters, then declares two variables rootList and nodeList. rootList contains top-level root nodes, and nodeList holds the remaining child nodes. The loop from lines 14 to 20 assigns values to those two variables. After that, the code further validates the data based on those variables. Once validated, it calls the internal function childrenNodeAdd, which is recursively invoked to add a child array named "children" to each node. The two arguments are rootNodeList and childrenList, representing the parent node set and all subsequent child nodes. On the first call at line 23, the top-level roots and all their descendants are passed in. Below is the annotated code snippet:

function childrenNodeAdd(rootNodeList, childrenList) {
      if (childrenList.length > 0) { // If there are no child nodes left, end the recursion
        // Iterate through the parent node set, find its children among the child nodes, and add them to the corresponding children array
        rootNodeList.forEach(function(rootNode) {
          rootNode["children"] = [];
          var childrenNodeList = childrenList.slice(0); // Copy the child nodes to store the remaining child nodes
          // Iterate over all child nodes
          childrenList.forEach(function(childrenNode, childrenIndex) {
            if (parentIdName in childrenNode && rootNode[nodeIdName] == childrenNode[parentIdName]) { // Root node's id equals the child's parent id
              rootNode["children"].push(childrenNode); // Add the matching node as a child
              childrenNodeList.splice(childrenIndex, 1); // Remove the assigned child from the remaining child nodes
            }
          });
          childrenNodeAdd(rootNode["children"], childrenNodeList); // Continue recursion for remaining child nodes; each recursion adds one level
        });
      }
    }

Tree structure => Two-dimensional structure

/**
 * Convert a tree-structured data set into a two-dimensional structure
 * @param  {String} childrenName The name used for child nodes in the tree structure
 * @param  {Array} treeData      The tree-structured data
 * @return {Array}               The converted common two-dimensional data
 */
function treeToList(childrenName, treeData) {
  var listData = [];
  transferTreeData(treeData);
  function transferTreeData (sourceData) {
     sourceData.forEach( function(node, nodeIndex) {
     if(node[childrenName].length > 0)
          transferTreeData(node[childrenName]);
      delete node[childrenName];
      listData.push(node);
     });
  }
  return listData;
}

This function can be tested by callingtreeToList("children", sourceData)to invoke it,sourceDatarefers to the tree-structure example given at the beginning of the article. The logic here is straightforward and will not be repeated.