CODEWITHSUNDEEP
reactjsfrontendgraph-algorithmdepth-first-search
Zazz
Zazz

Reputation: 381

D3JS/React - Construct Tree from a linked list with an arbitrary amount of children each level?

I am working on a visualization tool where i am trying to represent a set of nodes in a tree-like structure. In the backend:

Example:

A -> B -> (C -> null / D -> E/F/G)
(A has B as a child, B has C and D as children. C has no children, D has E/F/G as children)

I am using the React D3 Tree library for the visualization. Example data the tree accepts:

const myTreeData = [
  {
    name: 'Top Level',
   
    children: [
      {
        name: 'Level 2: A',
        children: [
           name: 'Level 3: C', 
          children:[
            name: 'Level 4: D', children: []
           ] 
      ]
      },
      {
        name: 'Level 2: B',
      },
    ],
  },
];

Ie. the nodes themselves contain an array with references to their own children.If they don't have any children, the array is empty.

I am having trouble figuring out what algorithm i need to use to convert my linked list to this tree-structure. Primarily, how to deal with the fact that each level can have an arbitrary amount of nodes. I've tried to do it iteratively by representing each "step" in the linked list as a level, then going backwards and linking each level to the one above it. However, the code gets very complicated and it's hard to generalize.

I suspect there is a very simple recursive solution to this problem, but i think the data structure used by the tree throws me off (having a hard time understanding how to pass that top-level children object around)

Upvotes: 1

Views: 179

Answers (1)

Zazz
Zazz

Reputation: 381

I managed to solve it. Its probably inefficient, but for whoevers curious:

  1. Start from the top node and recursively get the children for each node, and store them in a double array. Each item (array) in the array then represents a level in the tree, and each item in the second array contains the nodename and the nodes children. (ie [ [A - B] [B - (C, D)] [D - F, C] [F] ]
  2. Going backwards in this array: We know that if we are on level n and level n-1 only contains one node, then all of level n is level - 1s children. We then set node n - 1 children to equal n.
  3. If the previous level has more than one node, we have to find the right parent. For all nodes in the previous level (parents): Create an empty list, nodeChildren. Iterate over all of this levels nodes (children). If parents.children contain child.name, push child to nodeChildren. After iterating - set parent.children = nodeChildren. Now, the children-array of the parent will contain the node-information of the child rather than just the name. (name:A children: [B] ) - > (name:A children: [name B -children: C, D]
  4. For this to work, the last item of the array has to be modified before the iteration to match this structure. (F) -> (name: F children: [])
  5. After the iterarion, the first item of the array (level 0) will contain the information the D3-tree expects

Upvotes: 1

Related Questions