Creating nested array from flat array - Data Structure

Question

I need to create a nested array using the path as reference for the children. E.g: 4.1 is a child of 4, 4.1.1 is a child of 4.1, 4.2 is a child of 4... I have this flat array, with all the data and paths. How would be the best approach to create a nested array where the children are nested to its parent based on its path.

Input:

const list = [
  {
    location: 1,
    path: '4'
  },
  {
    location: 2,
    path: '4.1'
  },  
  {
    location: 3,
    path: '4.1.1'
  },  
  {
    location: 4,
    path: '4.1.2'
  },  
  {
    location: 5,
    path: '4.2'
  },  
  {
    location: 6,
    path: '4.2.1'
  },
  {
    location: 7,
    path: '4.3'
  },
  {
    location: 8,
    path: '4.3.1'
  }
];

Output:

const  list = [
  {
    location: 1,
    path: '4',
        children: [
            {
            location: 2,
            path: '4.1',
            children: [
                {
                    location: 3,
                    path: '4.1.1'
                },  
                {
                    location: 4,
                    path: '4.1.2'
                },  
            ]
        },  
            {
                location: 5,
                path: '4.2',
                children: [
                    {
                        location: 6,
                        path: '4.2.1'
                    },
                ]
            },  
            {
                location: 7,
                path: '4.3',
                children: [
                    {
                        location: 8,
                        path: '4.3.1'
                    }
                ]
            },
        ]
  },
];

The best approach would be something recursive. Any suggestions for this algorithm?

Answer 1

One way to do this is to use an intermediate index mapping paths to objects, then folding your list into a structure by looking up each node and its parent in the index. If there is no parent, then we add it to the root object. In the end, we return the children of our root object. Here's some code for that:

const restructure = (list) => {
  const index = list .reduce(
    (a, {path, ...rest}) => ({...a, [path]: {path, ...rest}}), 
    {}
  )
  
  return list .reduce((root, {path}) => {
    const node = index [path]
    const parent = index [path .split('.') .slice(0, -1) .join('.')] || root
    parent.children = [...(parent.children || []), node]
    return root
  }, {children: []}) .children
}

const list = [{location: 1, path: '4'}, {location: 2, path: '4.1' }, {location: 3, path: '4.1.1'}, {location: 4, path: '4.1.2'}, {location: 5, path: '4.2'}, {location: 6, path: '4.2.1'}, {location: 7, path: '4.3'}, {location: 8, path: '4.3.1'}]

console.log (restructure (list))

.as-console-wrapper {min-height: 100% !important; top: 0}

Using the index means that we don't have to sort anything; the input can be in any order.

Finding the parent involves replacing, for instance, "4.3.1" with "4.3" and looking that up in the index. And when we try "4", it looks up the empty string, doesn't find it and uses the root node.

If you prefer regex, you could use this slightly shorter line instead:

    const parent = index [path.replace (/(^|\.)[^.]+$/, '')] || root

---

But, you might also want to look at a more elegant technique in a recent answer on a similar question. My answer here, gets the job done (with a bit of ugly mutation) but that answer will teach you a lot about effective software development.

Answer 2

I was curious if the linked answer from Scott would be able to solve this problem without modification. It does!

import { tree } from './Tree'
import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const myTree =
  tree                          // <- make tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))

[
  {
    "location": 1,
    "path": "4",
    "children": [
      {
        "location": 2,
        "path": "4.1",
        "children": [
          {
            "location": 3,
            "path": "4.1.1",
            "children": []
          },
          {
            "location": 4,
            "path": "4.1.2",
            "children": []
          }
        ]
      },
      {
        "location": 5,
        "path": "4.2",
        "children": [
          {
            "location": 6,
            "path": "4.2.1",
            "children": []
          }
        ]
      },
      {
        "location": 7,
        "path": "4.3",
        "children": [
          {
            "location": 8,
            "path": "4.3.1",
            "children": []
          }
        ]
      }
    ]
  }
]

The Tree module is shared in this post and here's a peek at the Func module that supplies bind -

// Func.js
const identity = x => x

const bind = (f, ...args) =>
  f(...args)

const raise = (msg = "") => // functional throw
  { throw Error(msg) }

// ...

export { identity, bind, raise, ... }

Expand the snippet below to verify the results in your browser -

// Func.js
const bind = (f, ...args) =>
  f(...args)
  
// Index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v)
      , empty()
      )
      
// Tree.js
// import { index } from './Index'
function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
    
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

// Main.js
// import { tree } from './Tree'
// import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const list =
  [{location:1,path:'4'},{location:2,path:'4.1'},{location:3,path:'4.1.1'},{location:4,path:'4.1.2'},{location:5,path:'4.2'},{location:6,path:'4.2.1'},{location:7,path:'4.3'},{location:8,path:'4.3.1'}]

const myTree =
  tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))

Answer 3

You can first sort the array of objects by path so that the parent will always be before it's children in the sorted array. eg: '4' will be before '4.1'

Now, you can create an object where the keys are the paths. Let's assume '4' is already inserted in our object.

obj = {
  '4': {
    "location": 1,
    "path": "4",    
  }
}

When we process '4.1', we first check if '4' is present in our object. If yes, we now go into its children (if the key 'children' isn't present, we create a new empty object) and check if '4.1' is present. If not, we insert '4.1'

obj = {
  '4': {
    "location": 1,
    "path": "4",
    "children": {
      "4.1": {
        "location": 2,
        "path": "4.1"
      }
    }
  }
}

We repeat this process for each element in list. Finally, we just have to recursively convert this object into an array of objects.

Final code:

list.sort(function(a, b) {
  return a.path - b.path;
})

let obj = {}

list.forEach(x => {
  let cur = obj;
  for (let i = 0; i < x.path.length; i += 2) {
    console.log(x.path.substring(0, i + 1))
    if (x.path.substring(0, i + 1) in cur) {
      cur = cur[x.path.substring(0, i + 1)]
      if (!('children' in cur)) {
        cur['children'] = {}
      }
      cur = cur['children']
    } else {
      break;
    }
  }
  cur[x.path] = x;
})

function recurse (obj) {
  let res = [];
  Object.keys(obj).forEach((key) => {
    if (obj[key]['children'] !== null && typeof obj[key]['children'] === 'object') {
      obj[key]['children'] = recurse(obj[key]['children'])
    }
    res.push(obj[key])
  })
  return res;
}

console.log(recurse(obj));

Answer 4

was thinking along the same terms as Aadith but came up from an iterative approach. I think the most performant way to do it is to use a linked list structure and then flatten it though.

const list = [
  {
    location: 1,
    path: '4'
  },
  {
    location: 2,
    path: '4.1'
  },  
  {
    location: 3,
    path: '4.1.1'
  },  
  {
    location: 4,
    path: '4.1.2'
  },  
  {
    location: 5,
    path: '4.2'
  },  
  {
    location: 6,
    path: '4.2.1'
  },
  {
    location: 7,
    path: '4.3'
  },
  {
    location: 8,
    path: '4.3.1'
  }
];

let newList = [];
list.forEach((location) =>
{
  console.log('Handling location ',location);
  if(location.path.split('.').length==1)
  {
    location.children = [];
    newList.push(location);
  }
  else
  {
    newList.forEach(loc => {
      console.log('checking out: ',loc);
      let found = false;
      while(!found)
      {
        console.log(loc.path,'==',location.path.substring(0, location.path.lastIndexOf('.')));
        found = loc.path == location.path.substring(0, location.path.lastIndexOf('.'));
        if(!found)
        {
          for(let i=0;i<loc.children.length;i++)
          {
            let aloc = loc.children[i];

            found = aloc.path == location.path.substring(0, location.path.lastIndexOf('.'));
            if(found)
            {
              console.log('found it...', loc);
              location.children = [];
              aloc.children.push(location);
              break;
            }
          }

        }
        else
        {
          console.log('found it...', loc);
          location.children = [];
          loc.children.push(location);
        }
      }
    } );
  }
});

console.log(newList);

This was my quick and dirty way of how to go about it

Answer 5

Thank you for all the suggestions! I could definitely see really sophisticated solutions to my problem. By the end of the day, I've ended up creating my own "dirty" solution.

It is definitely a slower approach, but for my application this list won't be long to the point where i should be too worry about optimization.

I had simplified the flatted list for the purpose of my question. Although, in reality the list was a little more complex then that. I could also pass the path I want to find its children.

This is the solution that worked for me.

function handleNested(list, location) {
  return list.map((item) => {
    if (item.children && item.children.length > 0) {
      item.children = handleNested(item.children, location);
    }
    if (
      location.path.startsWith(item.path) &&
      location.path.split(".").length === item.path.split(".").length + 1
    ) {
      return {
        ...item,
        children: item.children ? [...item.children, location] : [location],
      };
    } else {
      return item;
    }
  });
}

function locationList(path) {
  // Filtering the list to remove items with different parent path, and sorting by path depthness.
  const filteredList = list
    .filter((location) => location.path.startsWith(path))
    .sort((a, b) => a.path.length - b.path.length);

  let nestedList = [];
  // Looping through the filtered list and placing each item under its parent.
  for (let i = 0; i < filteredList.length; i++) {
    // Using a recursive function to find its parent.
    let res = handleNested(nestedList, filteredList[i]);
    nestedList = res;
  }

  return nestedList;
}

locationList("4");