build tree from json array in javascript with no parent key but a prefix

Question

How would you build tree from a json array in javascript with no parent key or any reference id but by matching a prefix "- "?

The prefix is incremental upon the depth of tree. for e.g.

"- " = level one
"- - " = level two
"- - - " = level three
...

There are a few similar questions but no relevant answer has been found yet.

So far, I have done something like below:

var $json = [
  { "id":"11", "text":"CatOne" },
  { "id":"12", "text":"- CatOneSubCat1" },
  { "id":"13", "text":"- CatOneSubCat2" },
  { "id":"14", "text":"- - CatOneSubCat2SubCat1" },
  { "id":"15", "text":"- - CatOneSubCat2SubCat2" },
  { "id":"16", "text":"- CatOneSubCat3" },
  { "id":"17", "text":"CatTwo" },
  { "id":"18", "text":"CatThree" },
  { "id":"19", "text":"CatFour" },
  { "id":"20", "text":"- CatFourSubCat1" },
  { "id":"21", "text":"- CatFourSubCat2" },
  { "id":"22", "text":"CatFive" }
];

$(document).ready(function(){
  var $arr = [];
  var $str = "";
  var $prefix = "- "; 

  $.each( $json, function( key, value ) {
    value.children = [];
    // TODO: additional prefix should be appended upon the depth of tree
    if(!value.text.startsWith($prefix)) {
    	$arr.push(value);
    }
    else {
    	$arr[$arr.length - 1].children.push(value);
    }
  });
  $("#mypre").text(JSON.stringify($arr, null, 2));
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<pre id="mypre"></pre>

Result from the snippet above:

[
    { "id":"11", "text":"CatOne", "children":[
        { "id":"12", "text":"- CatOneSubCat1", "children":[] },
        { "id":"13", "text":"- CatOneSubCat2", "children":[] },
        { "id":"14", "text":"- - CatOneSubCat2SubCat1", "children":[] },
        { "id":"15", "text":"- - CatOneSubCat2SubCat2", "children":[] },
        { "id":"16", "text":"- CatOneSubCat3", "children":[] }
    ] },
    { "id":"17", "text":"CatTwo", "children":[] },
    { "id":"18", "text":"CatThree", "children":[] },
    { "id":"19", "text":"CatFour", "children":[
        {"id":"20", "text":"- CatFourSubCat1", "children":[] },
        {"id":"21", "text":"- CatFourSubCat2", "children":[] }
    ] },
    { "id":"22", "text":"CatFive", "children":[] }
]

Expected result:

[
    { "id":"11", "text":"CatOne", "children":[
        { "id":"12", "text":"- CatOneSubCat1", "children":[] },
        { "id":"13", "text":"- CatOneSubCat2", "children":[
            { "id":"14", "text":"- - CatOneSubCat2SubCat1", "children":[] },
            { "id":"15", "text":"- - CatOneSubCat2SubCat2", "children":[] }
        ]},
        { "id":"16", "text":"- CatOneSubCat3", "children":[] }
    ] },
    { "id":"17", "text":"CatTwo", "children":[] },
    { "id":"18", "text":"CatThree", "children":[] },
    { "id":"19", "text":"CatFour", "children":[
        { "id":"20", "text":"- CatFourSubCat1", "children":[] },
        { "id":"21", "text":"- CatFourSubCat2", "children":[] },
    ] },
    { "id":"22", "text":"CatFive", "children":[] }
]

There's no such thing as a JSON array. JSON is always a string. — Mulan
– Mulan, Commented Apr 21, 2017 at 7:37

Nina Scholz · Accepted Answer · 2017-04-21 09:25:18Z

1

You could use an array as reference for the last inserted level objects and iterate the given array whil checking the level.

var data = [{ id: "11", text: "CatOne" }, { id: "12", text: "- CatOneSubCat1" }, { id: "13", text: "- CatOneSubCat2" }, { id: "14", text: "- - CatOneSubCat2SubCat1" }, { id: "15", text: "- - CatOneSubCat2SubCat2" }, { id: "15a", text: "- - -     extra space" }, { id: "16", text: "- CatOneSubCat3" }, { id: "17", text: "CatTwo" }, { id: "18", text: "CatThree" }, { id: "19", text: "CatFour" }, { id: "20", text: "- CatFourSubCat1" }, { id: "21", text: "- CatFourSubCat2" }, { id: "22", text: "CatFive" }],
    tree = function (array) {
        var levels = [{}];
        data.forEach(function (a) {
            var level = Math.floor(a.text.match(/^(- )*/)[0].length / 2);
            levels.length = level + 1;
            levels[level].children = levels[level].children || [];
            levels[level].children.push(a);
            levels[level + 1] = a;
        });
        return levels[0].children;
    }(data);
  
console.log(tree);

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

edited Apr 21, 2017 at 9:25

answered Apr 21, 2017 at 7:27

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Aung Myo Linn Over a year ago

Math.floor("- - - SS".match(/^([ \-]*)+/)[0].length/2) returns 4 instead of 3, where S = "extra space".

Nina Scholz Over a year ago

what means extra space?

Aung Myo Linn Over a year ago

SO strips the extra spaces so S is used as a placeholder, please see this fiddle jsfiddle.net/rw25p8hh

Nina Scholz Over a year ago

i have now an object with extra space, { id: "15a", text: "- - - extra space" } it should work with a changed regex now.

Mulan · Accepted Answer · 2017-04-21 18:07:15Z

Here's one way you can do it using recursion.

I particularly like this answer because there is almost no mental overhead in the main aux loop. Because we're building a tree, it makes sense that our process branches off into several iterations of our loop to build the final result.

If the current node x is ever undefined or the node depth level decreases, we're done iterating for this depth
If the node depth level stayed the same, find all the nodes at the next depth level, and continue iterating at the current depth level
otherwise the node depth level increased and we will skip that node for the current depth

Aside from the little depth helper function I added (also recursive), there's nothing else to it.

// type Node = Node { id :: String, text :: String, nodes :: [Node] }

// depth :: Node -> Int
const depth = ({ text: [x, y, ...text] }) =>
  (x + y === '- ') ? 1 + depth({ text }) : 0

// buildTree :: [Node] -> [Node]
const buildTree = xs => {
  const aux = (d, [x,...xs]) => {
    if (x === undefined || depth(x) < d)
      return []
    else if (depth(x) === d)
      return [Object.assign({}, x, {nodes: aux(d+1, xs)}), ...aux(d, xs)]
    else
      return aux(d, xs) 
  }
  return aux(0, xs)
}

const nodes = [
  { id: '11', text: 'CatOne' },
  { id: '12', text: '- CatOneSubCat1' },
  { id: '13', text: '- CatOneSubCat2' },
  { id: '14', text: '- - CatOneSubCat2SubCat1' },
  { id: '15', text: '- - CatOneSubCat2SubCat2' },
  { id: '16', text: '- CatOneSubCat3' },
  { id: '17', text: 'CatTwo' },
  { id: '18', text: 'CatThree' },
  { id: '19', text: 'CatFour' },
  { id: '20', text: '- CatFourSubCat1' },
  { id: '21', text: '- CatFourSubCat2' },
  { id: '22', text: 'CatFive' }
]

const tree = buildTree(nodes)

console.log(JSON.stringify(tree, null, '  '))

Collectives™ on Stack Overflow

build tree from json array in javascript with no parent key but a prefix

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related