skip to Main Content

I have an array of objects. Each contains a "lv" property, which is an integer >= 0.

[
  {lv: 0, name: "A"},
  {lv: 1, name: "B"},
  {lv: 1, name: "C"},
  {lv: 2, name: "D"},
  {lv: 3, name: "E"},
  {lv: 1, name: "F"},
  {lv: 0, name: "G"},
]

This is exported from an old software and represents a tree structure: "lv" represents how deep the node is, and its place in the tree is always relative to the previous node in the array. So the first object (A) is level 0 (root); B is level 1, and therefore a child of the previous level 0 entry (A); C is also level 1, and therefore a sibling of B (and also a child of A); and so on. The resulting structure looks like this:

├ A
│ ├ B
│ ├ C
│ │ └ D
│ │   └ E
│ └ F
└ G

I want to write a function to transform this flat array into a structure that would more closely reflect the tree structure, like this:

[
  {
    name: "A",
    children: [
      {
        name: "B",
        children: null
      },
      {
        name: "C",
        children: [
          {
            name: "D",
            children: [
              {
                name: "E",
                children: null
              }
            ]
          }
        ]
      },
      {
        name: "F",
        children: null
      }
    ]
  },
  {
    name: "G",
    children: null
  }
]

So basically each node has its children listed in an array under the "children" property, recursively.

I wrote the following recursive function but it breaks when it encounters a node that goes back up the tree (eg. a level 1 node coming after a level 3 node):

function buildTree(arr) {
  let siblings = [], children = null

  while (arr.length) {
    let node = arr.shift()

    if (arr.length) {
      let nodeLv = +node.lv
      let nextNodeLv = +arr[0].lv
      if (nextNodeLv > nodeLv) {
        children = buildTree(arr)
      }
    }

    let newNode = {
      name: node.name,
      children: children
    }

    siblings.push(newNode)
  }

  return siblings
}

This gives me the following structure instead of the one pictured above:

└ A
  ├ B
  └ C
    └ D
      └ E
        └ F
          └ G

So basically it works fine when building deeper, but cannot go the other way (from E to F or F to G).

What am I doing wrong here? Is there a better way to approach this?

3

Answers


  1. Use a stack, where its current state represents a path to the current level, with node instances. Add the current node to the parent’s children list that sits at the top of the stack. Pop nodes from that stack when the level decreases.

    function makeHierarchy(flat) {
        const hierarchy = [];
        const stack = [{children: hierarchy}];
        for (const {lv, name} of flat) {
            while (lv < stack.length - 1) stack.pop();
            const obj = {name, children: []};
            stack.at(-1).children.push(obj);
            stack.push(obj);
        }
        return hierarchy;
    }
    
    // Demo with data from question
    const flat = [{lv: 0, name: "A"},{lv: 1, name: "B"},{lv: 1, name: "C"},{lv: 2, name: "D"},{lv: 3, name: "E"},{lv: 1, name: "F"},{lv: 0, name: "G"},];
    const hierarchy = makeHierarchy(flat);
    console.log(hierarchy);

    Note that here the leaf nodes have their children property set to an empty array. This seems more consistent than having null in that case. If you really need the null values, then use this variant:

    function makeHierarchy(flat) {
        const hierarchy = [];
        const stack = [{children: hierarchy}];
        for (const {lv, name} of flat) {
            while (lv < stack.length - 1) stack.pop();
            const obj = {name, children: null};
            (stack.at(-1).children ??= []).push(obj);
            stack.push(obj);
        }
        return hierarchy;
    }
    
    const flat = [{lv: 0, name: "A"},{lv: 1, name: "B"},{lv: 1, name: "C"},{lv: 2, name: "D"},{lv: 3, name: "E"},{lv: 1, name: "F"},{lv: 0, name: "G"},];
    const hierarchy = makeHierarchy(flat);
    console.log(hierarchy);
    Login or Signup to reply.
  2. This can be done without recursion. You can first determine the correct parent for each item, and then move each item into its correct place in the hierarchy.

    const data = [{"lv":0,"name":"A"},{"lv":1,"name":"B"},{"lv":1,"name":"C"},{"lv":2,"name":"D"},{"lv":3,"name":"E"},{"lv":1,"name":"F"},{"lv":0,"name":"G"}]
    
    // assign a parent to each item
    data.forEach((e, i, r) => {
      let last = r[i-1];
      if(last) {
        e.parent = last;
        for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
      }
    })
    
    // the result will directly contain the items with no parent
    let result = data.filter(e => !e.parent);
    
    // add each item to a children array created for its parent
    data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))
    
    // delete unnecessary propertoes
    data.forEach(e => {
      delete e.parent
      delete e.lv
      if(!e.children?.length) e.children = null
    })
    
    console.log(result)
    Login or Signup to reply.
  3. You don’t need a stack or recursion, just remember the last items of levels to put children to them:

    const arr = [
      {lv: 0, name: "A"},
      {lv: 1, name: "B"},
      {lv: 1, name: "C"},
      {lv: 2, name: "D"},
      {lv: 3, name: "E"},
      {lv: 1, name: "F"},
      {lv: 0, name: "G"},
    ]
    const result = [], last = [{children: result}]; // collect last nodes of levels
    for(const {lv, name} of arr){
      const node = {name, children: null};
      (last[lv].children ??= []).push(node);
      last[lv + 1] = node;
    }
    
    console.log(result);
    .as-console-wrapper{max-height:100%!important};

    And benchmarking:

    ` Chrome/125
    --------------------------------------------------------------------------------------
    >                 n=7       |       n=70        |       n=700       |      n=7000     
    Alexander   ■ 1.00x x1m 111 | ■ 1.00x x100k  84 | ■ 1.00x x100k 858 | ■ 1.00x x10k 942
    trincot       1.14x x1m 127 |   1.11x x100k  93 |   1.13x  x10k  97 |   1.16x  x1k 109
    Andrew        6.20x x1m 688 |   5.82x x100k 489 |   5.26x  x10k 451 |   5.98x  x1k 563
    -------------------------------------------------------------------------------------- `
    

    Open in the playground

    const $chunk = [
      {lv: 0, name: "A"},
      {lv: 1, name: "B"},
      {lv: 1, name: "C"},
      {lv: 2, name: "D"},
      {lv: 3, name: "E"},
      {lv: 1, name: "F"},
      {lv: 0, name: "G"},
    ]
    
    const $input = [], arr = $input, data = $input;
    
    // @benchmark Alexander
    const result = [], last = [{children: result}]; // collect last nodes of levels
    for(const {lv, name} of arr){
      const node = {name, children: null};
      (last[lv].children ??= []).push(node);
      last[lv + 1] = node;
    }
    result;
    
    // @benchmark trincot
    function makeHierarchy(flat) {
        const hierarchy = [];
        const stack = [{children: hierarchy}];
        for (const {lv, name} of flat) {
            while (lv < stack.length - 1) stack.pop();
            const obj = {name, children: null};
            (stack.at(-1).children ??= []).push(obj);
            stack.push(obj);
        }
        return hierarchy;
    }
    
    makeHierarchy(arr);
    
    // @benchmark Andrew
    {
    // assign a parent to each item
    data.forEach((e, i, r) => {
      let last = r[i-1];
      if(last) {
        e.parent = last;
        for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
      }
    })
    
    // the result will directly contain the items with no parent
    let result = data.filter(e => !e.parent);
    
    // add each item to a children array created for its parent
    data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))
    
    // delete unnecessary propertoes
    data.forEach(e => {
      delete e.parent
      delete e.lv
      if(!e.children?.length) e.children = null
    })
    result;
    }
    
    /*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search