solution.js

// creates a graph representation of the input list
function createRelationshipGraph(inputList, idsOnly) {
  const graph = {};

  inputList.forEach(curNode => {
    const { id: curId, parent_id: parentId } = curNode;
    const parentDoesNotExist = typeof graph[parentId] === "undefined";
    const curDoesNotExist = typeof graph[curId] === "undefined";
    const parentIsTopLevel = parentId === null;

    // initialize the parent graph for the first time
    if (parentDoesNotExist) {
      graph[parentId] = {};
    }
    // add the node to the parent graph
    graph[parentId][curId] = idsOnly ? true : curNode;

    // if the current node is a top level node, add itself to the graph
    // if we don't do this, we may miss top level nodes with no children 
    if (parentIsTopLevel && curDoesNotExist) {
      graph[curId] = {};
    }
  });

  return graph;
}

// walks the graph and builds the output list simultaneously
function walkSubGraph(graph, startId) {
  let output = [];
  const isLeafNode = typeof graph[startId] === 'undefined';
  if (isLeafNode) {
    return output;
  }
  Object.keys(graph[startId]).forEach(curId => {
    const curNode = graph[startId][curId];
    output.push(curNode);
    walkSubGraph(graph, curId).forEach(childNode => output.push(childNode));
  });

  return output;
}

module.exports = function sortCategoriesForInsert(inputJson) {
  const inputList = JSON.parse(inputJson);
  const relGraph =  createRelationshipGraph(inputList, false);
  const output = walkSubGraph(relGraph, null);
  return JSON.stringify(output);
}