Example of converting JavaScript flat array to tree structure

10,000 pieces of data were lost in the background

No matter how much I planned, I still couldn't escape it. The backend really threw tens of thousands of data to the frontend at once. Well, at least it’s not 100,000 yet. As shown below, the background returns the following structure:

const flatArr = [
  { id: '001', name: 'Node 1' },
  { id: '0011', parentId: '001', name: 'Node 1-1' },
  { id: '00111', parentId: '0011', name: 'Node 1-1-1' },
  { id: '002', name: 'Node 2' },
]

As you can see, this is actually a flat array. Our requirement is to render such data in the cascade selector of Element-ui, which receives the following tree structure:

let options = [
  {
    value: 'zhinan',
    label: 'Guide',
    children: [
      {
        value: 'shejiyuanze',
        label: 'Design principles',
        children: [
          { value: 'yizhi', label: 'consistent' },
          { value: 'fankui', label: 'Feedback'}
        ],
      }
    ]
  }
]

Oh my god, this requires me to convert the flat array into a tree structure!
The operation was as fierce as a tiger, and recursion was written without saying a word.

Recursive method

It’s done, the code is concise, the idea is clear, and when it runs, what? The page is stuck. According to console.time(), it took about 18 seconds to calculate the tree structure we need.
I reflected on myself. There are tens of thousands of data. Every time I recursively search for the child nodes of the parent node from bottom to top, I need to traverse the array once, which is of course time-consuming! Moreover, the calculation time has obviously caused the page to freeze, so this method is definitely not advisable. So, is there a better solution?

Non-recursive method

Here, we cleverly apply the feature that objects store references. Each time, the id of the current node is used as the key to save the reference information of the corresponding node. When traversing the array, the children information of objMap is updated each time. In this way, all nodes and their child nodes are retained in objMap. Most importantly, we only need to traverse the array once, and the time complexity is O(n). Using this method, the calculation time only takes 60ms!

Summarize

• Recursive method: Each time you recursively search for the child nodes of the current node, you need to traverse the array again, and the time complexity is O(nlogn)
• Non-recursive method: Search for child nodes from the root node downwards, save the information of each node and its child nodes through Map, the child nodes save the references on the Map, the child nodes of each node can be found in the Map by id, the time complexity is O(n)

Let's look at a comparison chart:

From the above trend of time complexity increasing with the amount of data, we can see that when the data becomes larger and larger, the time consumed by the recursive algorithm will be much greater than that of the non-recursive algorithm. Therefore, when the amount of data is small, using a recursive algorithm has certain advantages, but when the data is large to a certain extent, the disadvantages of the recursive approach will become more and more obvious, and using a non-recursive algorithm will be much faster!

Finally, I have to say that through this comparison, we can clearly feel the importance of algorithms. Different implementation methods can have huge differences, which deserves the attention of every developer!

This is the end of this article about the implementation example of converting JavaScript flat array to tree structure. For more relevant content about converting JavaScript flat array to tree structure, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope you will support 123WORDPRESS.COM in the future!