Javascript nested array get elements

Question

I have an array like:

"pages": [{
    "key": "1",
    "pages": [{
        "key": "2",
        "pages": [{
            "key": "3"
        }]
    },
        {
            "key": "4",
            "pages": [{
                "key": "5"
            }]

        }]
}]

where key 1 and 4 are at same level and 1 contains 2 which contains 3 and the key 4 contains 5. The result I want is in the order [3,2,5,1,4]. I have tried the following recursion but i am not able to get the correct order.

 function fnGetAll (oTopDetailPage, array) {
    var i;

    for (i=0; i<oTopDetailPage.length; i++) {
        array.push(oTopDetailPage[i]);
        if(oTopDetailPage[i].pages) {
            fnGetAllSubPages(oTopDetailPage[i].pages, array);
        }
    }
    return array;
}

The output you are going for doesn't really make sense. Can you change what you are expecting? Maybe an object with the parent page and then the children like { 1: [2, 3], 4: [5] }. Why do you need to output you are requesting ? — pizzarob
– pizzarob, Commented Apr 21, 2017 at 20:35
If you add another page, with say, a "key" of "6", within the pages property of the object with a "key" of "1", where would that fall in your output and why? — Heretic Monkey
– Heretic Monkey, Commented Apr 21, 2017 at 20:42
To those wondering where the order comes from: it looks like boomcode is trying to get each level from lowest to highest: Level 1: [1,4], Level 2: [2,5], Level 3 [3], Level 3, Level 2, Level 1 -> 3,2,5,1,4 — Patrick Barr
– Patrick Barr, Commented Apr 21, 2017 at 20:46
@PatrickBarr from the code above 1 and 4 are not on the same level. 4 is nested inside 1. — Junius L
– Junius L, Commented Apr 21, 2017 at 21:00

Nina Scholz · Accepted Answer · 2017-04-22 11:31:49Z

5

If you want a Depth-first search, you could iterate the children first and then take the actual key.

The result is an array, which is a bit different, then the given array.

function getDepthFirst(object) {
    var result = [];
    object.pages.forEach(function iter(a) {
        Array.isArray(a.pages) && a.pages.forEach(iter);
        result.push(a.key);
    });
    return result;
}

var data = { pages: [{ key: 1, pages: [{ key: 2, pages: [{ key: 3 }] }, { key: 4, pages: [{ key: 5 }] }] }] };
  
console.log(getDepthFirst(data)); // [3, 2, 5, 4, 1]

Addendum for getting a reverse level order traversal result of [3, 5, 2, 4, 1], with a temporary array, which collects all data from the same level and return an array with items from all levels, starting from the highest to the lowest.

The callback uses a closure over the actual level.

function getData(object) {
    var temp = [];
    object.pages.forEach(function iter(level) {
        return function (a) {
            Array.isArray(a.pages) && a.pages.forEach(iter(level + 1));
            temp[level] = temp[level] || [];
            temp[level].push(a.key);
        };
    }(0));
    return temp.reduceRight(function (r, a) {
        return r.concat(a);
    });
}

var data = { pages: [{ key: 1, pages: [{ key: 2, pages: [{ key: 3 }] }, { key: 4, pages: [{ key: 5 }] }] }] };

console.log(getData(data)); // [3, 5, 2, 4, 1]

edited Apr 22, 2017 at 11:31

answered Apr 21, 2017 at 21:01

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

2 Comments

boomcode Over a year ago

Thanks :) Is the post order traversal possible like [3,5,2,4,1] ?

Nina Scholz Over a year ago

@boomcode, it is possible. the name is reverse level order traversal, please see edit.

Mulan · Accepted Answer · 2017-04-21 21:32:42Z

1

Your root container is a little weird because it's invalid javascript. I'm assuming it's {pages: ... } with enclosing {} but even that doesn't make sense because the root container doesn't contain a key property.

You should first fix your nodes such that you have a uniform construction, eg

type Node = Node { key: String, pages: [Node] }

Then implementing your depth-first search is trivial

const dfs = ({key, pages = []}) =>
  [...pages.reduce((acc, p) => acc.concat(dfs(p)), []), key]
  
const data = {
  "key": "1",
  "pages": [{
      "key": "2",
      "pages": [{
          "key": "3"
      }]
  },
  {
      "key": "4",
      "pages": [{
          "key": "5"
      }]
  }]
}
  
console.log(dfs(data))
// [ '3', '2', '5', '4', '1' ]

If you were constructing data by-hand, don't. Instead, I suggest you make a simple constructor to build the data uniformly. Because each node is now guaranteed to have a key and pages property, we can remove the default parameter value for pages = [] in dfs. This is better because we can avoid any defensive programming that might try to accommodate for the missing property.

const dfs = ({key, pages}) =>
  [...pages.reduce((acc, p) => acc.concat(dfs(p)), []), key]
  

const makeNode = (key, ...pages) => ({key, pages})

const data =
  makeNode('1',
    makeNode('2',
      makeNode('3')),
    makeNode('4',
      makeNode('5')))
  
console.log(dfs(data))
// [ '3', '2', '5', '4', '1' ]

edited Apr 21, 2017 at 21:32

answered Apr 21, 2017 at 21:26

Mulan

136k35 gold badges240 silver badges276 bronze badges

2 Comments

Nina Scholz Over a year ago

hm ... :) shorter looks better.

Mulan Over a year ago

@NinaScholz <3 <3 it only works though because I forced the root node to contain a key property, otherwise calling my function would be pretty weird.

Collectives™ on Stack Overflow

Javascript nested array get elements

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related