Build nested object array from recursive function-CodePudding

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 
}

CodePudding user response：

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)

CodePudding user response：

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.

CodePudding user response：

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; }