Build nested object array from recursive function

Question

How would i utilize my getChildren() function to create a larger function which takes my two main arrays objs and objRefs and outputs a single array of objs demonstrating their parent/child relationship.

here are the two main data arrays

const objs = [
    { name: "Kevin", age: 5, id: 1 },
    { name: "Matt", age: 53, id: 5 },
    { name: "Marry", age: 30, id: 2 },
    { name: "Leslie", age: 21, id: 3 },
    { name: "Sarah", age: 46, id: 4 },
    { name: "Heather", age: 37, id: 6 },
    { name: "Cory", age: 19, id: 7 },
]

const objRefs = [
    { parent_id: 5, obj_id: 7 }, // cory child of matt
    { parent_id: null, obj_id: 6 }, // matt root
    { parent_id: null, obj_id: 4 }, // sarah root
    { parent_id: null, obj_id: 5 }, // heather root
    { parent_id: 5, obj_id: 3 }, // leslie child of matt
    { parent_id: 4, obj_id: 2 }, // mary child of sarah
    { parent_id: 3, obj_id: 1 }, // kevin child of leslie
]

My goal is to run a function called getFamilyTree() which would return me this...

const tree = [
    {
        id: 5,
        name: "Matt",
        age: 53,
        children:[ 
            {
                id: 3,
                name: "Leslie",
                age: 21,
                children:[ 
                    {
                        id: 1,
                        name: "Kevin",
                        age: 5,
                        children:[ ]
                    }
                ]
            },
            {
                id: 7,
                name: "Cory",
                age: 19,
                children:[ ]
            }
        ]
    },
    {
        id: 6,
        name: "Heather",
        age: 37,
        children:[ ]
    },
    {
        id: 4,
        name: "Sarah",
        age: 46,
        children:[ 
            {
                id: 2,
                name: "Marry",
                age: 30,
                children:[ ]
            }
        ]
    }
]

I have a function that returns me all the children for the given parent node id, but im not sure how structure a function to return me the entire tree like my example.

function getChildren(parent_id) {
    let children = []
    for (var i = 0; i < objRefs.length; i++) {
        const ref = objRefs[i]
        if (ref.parent_id === parent_id) {
            const obj = objs.find(obj => {
                return obj.id === ref.obj_id
            })
            children.push(obj)
        }
    }
    return children
}

function getFamilyTree() {
    let result = []
    ... // build recursive family tree
    return result 
}

do you need to use a recursive function?

Nina Scholz
– Nina Scholz

2022-02-16 15:59:56 +00:00
Commented Feb 16, 2022 at 15:59 — Nina Scholz
– Nina Scholz, Commented Feb 16, 2022 at 15:59
no. just figured it would be necessary

JokerMartini
– JokerMartini

2022-02-16 16:26:34 +00:00
Commented Feb 16, 2022 at 16:26 — JokerMartini
– JokerMartini, Commented Feb 16, 2022 at 16:26

FZs · Accepted Answer · 2022-02-16 16:21:18Z

You don't need a recursive function to construct that.

To get a reasonable time complexity, store all the objs to a Map or something (if the ids are sequential, even an array will work) keyed by id. Then, just iterate over objRefs and construct the relations appropriately:

const objs = [
    { name: "Kevin", age: 5, id: 1 },
    { name: "Matt", age: 53, id: 5 },
    { name: "Marry", age: 30, id: 2 },
    { name: "Leslie", age: 21, id: 3 },
    { name: "Sarah", age: 46, id: 4 },
    { name: "Heather", age: 37, id: 6 },
    { name: "Cory", age: 19, id: 7 
},
]

const objRefs = [
    { parent_id: 5, obj_id: 7 }, // cory child of matt
    { parent_id: null, obj_id: 6 }, // matt root
    { parent_id: null, obj_id: 4 }, // sarah root
    { parent_id: null, obj_id: 5 }, // heather root
    { parent_id: 5, obj_id: 3 }, // leslie child of matt
    { parent_id: 4, obj_id: 2 }, // mary child of sarah
    { parent_id: 3, obj_id: 1 }, // kevin child of leslie
]


function getFamilyTree(objs, objRefs){

    const tree = []

    const map = new Map(
        objs.map(e => [e.id, { ...e, children: [] }])
    )

    for(const {parent_id, obj_id} of objRefs){
        if(parent_id === null){
            tree.push(map.get(obj_id))
        }else{
            map.get(parent_id).children.push(map.get(obj_id))
        }
    }

    return tree
}

const tree = getFamilyTree(objs, objRefs)

console.log(tree)

jkoestinger · Accepted Answer · 2022-02-16 16:06:19Z

I don't think you even need the getChildren function to actually build your tree. Using Maps instead could be useful:

const objs = [
    { name: "Kevin", age: 5, id: 1 },
    { name: "Matt", age: 53, id: 5 },
    { name: "Marry", age: 30, id: 2 },
    { name: "Leslie", age: 21, id: 3 },
    { name: "Sarah", age: 46, id: 4 },
    { name: "Heather", age: 37, id: 6 },
    { name: "Cory", age: 19, id: 7 },
]

const objRefs = [
    { parent_id: 5, obj_id: 7 }, // cory child of matt
    { parent_id: null, obj_id: 6 }, // matt root
    { parent_id: null, obj_id: 4 }, // sarah root
    { parent_id: null, obj_id: 5 }, // heather root
    { parent_id: 5, obj_id: 3 }, // leslie child of matt
    { parent_id: 4, obj_id: 2 }, // mary child of sarah
    { parent_id: 3, obj_id: 1 }, // kevin child of leslie
]

function getFamillyTree(){
  const nodes = new Map()

  // Preparing the data nodes
  objs.forEach(elt => nodes.set(elt.id, {...elt, children: [], root: false}))

  // Linking the nodes to make the parent <-> children relations
  objRefs.filter(rel => !!rel.parent_id).forEach(rel => {
    const parent = nodes.get(rel.parent_id)
    parent.children.push(nodes.get(rel.obj_id))
  })
  
  // Marking the roots
  objRefs.filter(rel => rel.parent_id === null).forEach(rel => {
    const obj = nodes.get(rel.obj_id)
    obj.root = true
  })
  return Array.from(nodes.values()).filter(obj => obj.root)
}

document.write(JSON.stringify(getFamillyTree(), null, 4))

Edit: This answer can be slightly off, because as Nina stated in a comment on the question, OP seems to ask for an explicitly recursive solution, leaving this here for reference.

why do you say this is slightly off? You don't have to do recursive function if it's not needed.

Nina Scholz · Accepted Answer · 2022-02-16 16:34:35Z

You could use some object as reference to the persons and their relations and map the nodes with their children.

const
    getChildren = parent => (references[parent] || []).map(id => ({
        ...nodes[id],
         children: getChildren(id)
    })),
    people = [{ name: "Kevin", age: 5, id: 1 }, { name: "Matt", age: 53, id: 5 }, { name: "Marry", age: 30, id: 2 }, { name: "Leslie", age: 21, id: 3 }, { name: "Sarah", age: 46, id: 4 }, { name: "Heather", age: 37, id: 6 }, { name: "Cory", age: 19, id: 7 }],
    children = [{ parent_id: 5, obj_id: 7 }, { parent_id: null, obj_id: 6 }, { parent_id: null, obj_id: 4 }, { parent_id: null, obj_id: 5 }, { parent_id: 5, obj_id: 3 }, { parent_id: 4, obj_id: 2 }, { parent_id: 3, obj_id: 1 }],
    nodes = Object.fromEntries(people.map(o => [o.id, o])),
    references = children.reduce((r, { parent_id, obj_id }) => ((r[parent_id] ??= []).push(obj_id), r), {}),
    tree = getChildren(null);
    
console.log(tree);

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

An approach with a single loop of children.

const
    getTree = (people, children, root) => {
        const
            nodes = Object.fromEntries(people.map(o => [o.id, o])),
            t = {};

       children.forEach(({ parent_id: p, obj_id: id }) => 
           ((t[p] ??= {}).children ??= []).push(Object.assign(t[id] ??= {}, nodes[id]))
       );
       return t[root].children;
    },
    people = [{ name: "Kevin", age: 5, id: 1 }, { name: "Matt", age: 53, id: 5 }, { name: "Marry", age: 30, id: 2 }, { name: "Leslie", age: 21, id: 3 }, { name: "Sarah", age: 46, id: 4 }, { name: "Heather", age: 37, id: 6 }, { name: "Cory", age: 19, id: 7 }],
    children = [{ parent_id: 5, obj_id: 7 }, { parent_id: null, obj_id: 6 }, { parent_id: null, obj_id: 4 }, { parent_id: null, obj_id: 5 }, { parent_id: 5, obj_id: 3 }, { parent_id: 4, obj_id: 2 }, { parent_id: 3, obj_id: 1 }],
    tree = getTree(people, children, null);
    
console.log(tree);

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

Collectives™ on Stack Overflow

Build nested object array from recursive function

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related