How do I sort an object with children properties?

Question

I have an object that represents a tree:

const obj = {
  "1": {
    id: "1",
    children: ["1-1", "1-2"]
  },
  "1-1": {
    id: "1-1",
    children: ["1-1-1", "1-1-2"]
  },
  "1-2": {
    id: "1-2",
    children: []
  },
  "1-1-1": {
    id: "1-1-1",
    children: []
  },
  "1-1-2": {
    id: "1-1-2",
    children: []
  }
};

The result is a list similar to:

What I need is to transform the object above to an array where items go in the order they do in the list representation, i.e. ['1', '1-1', '1-1-1', '1-1-2', '1-2']. Ids can be any so I can't rely on them. It's the order of items in the children property that matters.

Update

The final result should be ['1', '1-1', '1-1-1', '1-1-2', '1-2'] i.e. the order they come in the list from the top to the bottom.

user_10153945 · Answer

const obj={1:{id:"1",children:["1-1","1-2"]},"1-1":{id:"1-1",children:["1-1-1","1-1-2"]},"1-2":{id:"1-2",children:[]},"1-1-1":{id:"1-1-1",children:[]},"1-1-2":{id:"1-1-2",children:[]}};

const output = Object.keys(obj)
// remove every non root
Object.entries(obj).forEach(el => el[1].children.forEach(child => {
  let index = output.indexOf(child)
  if (index !== -1) {
    output.splice(index, 1)
  }
}))

for (let i = 0; i < output.length; i++) {
  // for each get it's children
  let children = obj[output[i]].children
  // push them just behind it
  output.splice(i + 1, 0, ...children)
}

console.log(output)

user_8595750 · Answer

I use DFS to parse. It can sort any depth data. (You can try the obj2)

const obj = {
  "1": {
    id: "1",
    children: ["1-1", "1-2"]
  },
  "1-1": {
    id: "1-1",
    children: ["1-1-1", "1-1-2"]
  },
  "1-2": {
    id: "1-2",
    children: []
  },
  "1-1-1": {
    id: "1-1-1",
    children: []
  },
  "1-1-2": {
    id: "1-1-2",
    children: []
  }
};

const obj2 = {
  "2": {
    id: "2",
    children: ["2-1", "2-2", "2-3"]
  },
  "2-1": {
    id: "2-1",
    children: ["2-1-1", "2-1-2"]
  },
  "2-2": {
    id: "2-2",
    children: []
  },
  "2-3": {
    id: "2-3",
    children: []
  },
  "2-1-1": {
    id: "2-1-1",
    children: ["2-1-1-1", "2-1-1-2"]
  },
  "2-1-2": {
    id: "2-1-2",
    children: ["2-1-2-1"]
  },
  "2-1-1-1": {
    id: "2-1-1-1",
    children: []
  },
  "2-1-1-2": {
    id: "2-1-1-2",
    children: []
  },
  "2-1-2-1": {
    id: "2-1-2-1",
    children: []
  },
};

/* DFS */
function sort(id) {
  if (!sorted.includes(id)) {
    sorted.push(id);
    obj[id].children.forEach(sub => {
      sort(sub);
    });
  }
}

/* MAIN */

let sorted = [];

for (let [id, value] of Object.entries(obj)) {
  sort(id);
}

console.log(sorted.flat());

user_6655160 · Answer

You could try a recursive call with the base condition to ignore the traversed node

const obj = {
  "1": {
    id: "1",
    children: ["1-1", "1-2"],
  },
  "1-1": {
    id: "1-1",
    children: ["1-1-1", "1-1-2"],
  },
  "1-2": {
    id: "1-2",
    children: [],
  },
  "1-1-1": {
    id: "1-1-1",
    children: [],
  },
  "1-1-2": {
    id: "1-1-2",
    children: [],
  },
}

function traverse(obj) {
  const res = []
  const traversed = {}

  function getChildren(id) {
    if (traversed[id]) {
      return
    }
    res.push(id)
    traversed[id] = true
    obj[id].children.forEach((childId) => getChildren(childId))
  }

  for (const id in obj) {
    getChildren(id)
  }

  return res
}

console.log(traverse(obj))

user_6418673 · Answer

Hope this is what you are expecting ?

  let ans = []
  function recursiveCallObj(key){
    !ans.includes(key) ? ans.push(key)  : ""
    for(let i=0; i< obj[key].children.length; i++){
      if(!ans.includes(obj[key].children[i])){
        recursiveCallObj(obj[key].children[i])
      }
      else{
        return
      }
    }
  }
  for(let [key, value] of Object.entries(obj)){
    if(value.children.length > 0){
      recursiveCallObj(key)
    }
    else{
      !ans.includes(key) ? ans.push(key)  : ""
    }
  }
  console.log(ans)

How do I sort an object with children properties?

Update

4 Answers