Convert 1D array sorted by ASCII order to a nested array in Javascript

Question

Assume this below array of objects that sorted by code property in ascii order:

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

How can I convert this to a nested array like this :

var nestedCodes = [
    {
        code: '01',
        children: [
            { code: '0101' },
            {
                code: '0102',
                children: [
                    { code: '010201' }
                ]
            },
            { code: '0103' }
        ]
    },
    {
        code: '02',
        children: [
            { code: '0201' },
            { code: '0202' }
        ]
    }
];

The structure of codes is like concatenating multiple 0N that N can be a number between 1 and 9. Note that codes come from server and there would be some additional properties beside code like title but it doesn't matter in this problem.

The main idea here is to make an appropriate format for jsTree.

Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one. — Yangshun Tay
– Yangshun Tay, Commented Nov 27, 2018 at 6:48
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting. — Amir
– Amir, Commented Nov 27, 2018 at 7:16
It's an interesting question. Have come up with an answer! (: — Yangshun Tay
– Yangshun Tay, Commented Nov 27, 2018 at 7:28

slider · Accepted Answer · 2018-11-27 07:03:59Z

You can do this with a recursive solution. The idea is to maintain the path (obtained as an array via String.prototype.match with a regex) and the parent under which you want to insert the code for each recursive call.

The parent keeps track of the node you want to pick in the "current" recursive call, and path helps in building the parent as you keep going deeper:

function insert(d, path, parent, arr) {
  if (path.length === 0) {
    arr.push(Object.assign({}, d));
    return;
  }
  var target = arr.find(e => e.code === parent);
  target.children = target.children || [];
  insert(d, path.slice(1), parent + path[0], target.children);
}

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

var res = codes.reduce((a, c) => {
  var p = c.code.match(/(0[1-9])/g);
  insert(c, p.slice(1), p[0], a);
  return a;
}, []);

console.log(res);

The assumption, of course, is that when a code is being inserted, its parent has already been inserted before.

Ahmad · Accepted Answer · 2018-11-27 07:09:49Z

I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here

But to do that, you must first add parent property to each of your codes array. I did that on the assumption that each code has a parent that is equivalent to the code itself except for the last two bytes.

var codes = [{code: '01'    },
             {code: '0101'  },
             {code: '0102'  },
             {code: '010201'},
             {code: '0103'  },
             {code: '02'    },
             {code: '0201'  },
             {code: '0202'  },
          ];

// add parents to each code
codes.forEach(function(c) {
  if (c.code.length > 2) {
    c.parent = c.code.substr(0, c.code.length - 2);
  } else {
    c.parent = 'root';
  }
});



function find_children(arr, parent) {
  var out = [];
  for (var i in arr) {
    
    if (arr[i].parent == parent) {
      
      var children = find_children(arr, arr[i].code);

      if (children.length) {
        arr[i].children = children;
      }
      out.push(arr[i])
    }
  }
  return out;
}

var nested = find_children(codes,'root');
console.log(nested);

Yangshun Tay · Accepted Answer · 2018-11-27 07:39:01Z

1

The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01 to exist to process 0102 (in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.

Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.

I also make heavy use of recursion since recursion is well suited for creating and traversing trees.

Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).

Just copy the format function into your code and it should be good to use.

const codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

function format(codes) {
  // Splits the string into an array of 2-character strings.
  const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
  const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));

  // 1. Represent the data as a tree which is more efficient to build.
  const tree = {};
  function createTree(tree, fragments) {
    let node = tree;
    fragments.forEach(fragment => {
      if (!node[fragment]) {
        node[fragment] = {};
      }
      node = node[fragment];
    });
  }
  codeFragments.forEach(fragments => createTree(tree, fragments));
  /* tree will have the structure:
  {
    "01": {
      "01": {},
      "02": {
        "01": {}
      },
      "03": {}
    },
    "02": {
      "01": {},
      "02": {}
    }
  }
  */

  // 2. Convert the tree structure into the desired format.
  function generateCodesFromTree(tree, previous) {
    const nestedCodes = [];
    Object.keys(tree).forEach(treeNode => {
      const code = previous + treeNode;
      const children = generateCodesFromTree(tree[treeNode], code);
      const nestedCode = { code };
      if (children.length > 0) {
        nestedCode.children = children;
      }
      nestedCodes.push(nestedCode);
    });
    return nestedCodes;
  }

  return generateCodesFromTree(tree, '');
}

console.log(format(codes));

edited Nov 27, 2018 at 7:39

answered Nov 27, 2018 at 7:21

Yangshun Tay

53.7k34 gold badges126 silver badges150 bronze badges

2 Comments

Amir Over a year ago

I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr

Yangshun Tay Over a year ago

@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's 010201, there will be a 0102 present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.

Joven28 · Accepted Answer · 2018-11-27 06:55:37Z

0

It can only be achieved by using a recursive approach. Try this one.

let codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

roots = codes.filter(c => c.code.length === 2);

roots.forEach(c => assign(c));

console.log(roots);

function assign(code) {
  codes.forEach(c => {
    if (c !== code) {
      if (code.code === c.code.slice(0, code.code.length)) {
        code.children = !code.children ? [c] : [...code.children, c];
        assign(code.children[code.children.length - 1]);
      }
    }
  });
}

edited Nov 27, 2018 at 6:55

answered Nov 27, 2018 at 6:50

Joven28

7693 silver badges12 bronze badges

Collectives™ on Stack Overflow

Convert 1D array sorted by ASCII order to a nested array in Javascript

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related