denormalize a list of nodes.

denormalizeNodes.ts

/*
Developer notes:
Written in Typescript.

I chose to use an iterative approach because it's able to handle more data than a recursive approach
before hitting a stackoverfow error.

This algorithm runs in O(N) time and O(N) space, while avoiding cycles without actively searching for them. 
Actively checking for cycles would make the time compexity O(NlogN).

The algorithm is mostly functional, and mostly immutable. It is straight forward to make it entirely
immutable and functional via a library like immutableJS, however since a constraint of this assignment is
to not use any libraries I opted not to. 

Meanwhile cloning maps using Object.assign() via vanilla JS takes O(N) time, so I opted to mutate maps 
instead of doing expensive clones for brownie points. The same clone can be done in O(1) via ImmutableJS.
*/


interface NodeContainer {
  node: Node,
  children: NodeContainer[]
}

interface Node {
  id: string
  parent_id: string
}

function unnormalizeNodes(nodes: Node[]) {
  // Stores the final structure of node containers to be returned.
  const nodeMap = new Map<string, NodeContainer>()
  // Stores a list of children's ids for every node.
  const nodeChildMap = new Map<string, string[]>()
  let rootNodeStack: NodeContainer[] = []
  let unusedNodesCounter = nodes.length

  for (let i = 0; i < nodes.length; ++i) {
    const node = nodes[i]

    if (node.id === node.parent_id) throw new Error(`Node cannot be its own parent: ${node.id}`)

    // Creates this nodes entry in node map.
    const newNodeContainer = createNodeContainer(node)
    nodeMap.set(node.id, newNodeContainer)

    // Adds node to root stack if it's a root.
    // Otherwise, creates or updates parent entry in parentChildMap as needed
    if (!node.parent_id) {
      rootNodeStack.push(newNodeContainer)
    } else if (!nodeChildMap.get(node.parent_id)) {
      const children = [node.id]
      nodeChildMap.set(node.parent_id, children)
    } else {
      nodeChildMap.get(node.parent_id).push(node.id)
    }
  }

  let childNodeStack = []
  let output = []
  for (let rootIndex = 0; rootIndex < rootNodeStack.length; ++rootIndex) {
    const root = rootNodeStack[rootIndex]
    childNodeStack = nodeChildMap.get(root.node.id) || []

    --unusedNodesCounter
    while (childNodeStack.length > 0) {
      const currentNodeId = childNodeStack.pop()
      const currentNode = nodeMap.get(currentNodeId)
      --unusedNodesCounter
    
      const nextChildren = nodeChildMap.get(currentNodeId)

      if (!nextChildren || nextChildren.length === 0) {
        bubbleUpChildren(currentNode, nodeMap, nodeChildMap)
      } else {
        for (let childIndex = 0; childIndex < nextChildren.length; ++childIndex) {
          childNodeStack.push(nextChildren[childIndex])
        }
      }
    }
    output.push(nodeMap.get(root.node.id))
  }

  // If the algorithm does not use all the nodes, then there must be one or more cycles without root nodes.
  if (unusedNodesCounter !== 0) {
    throw new Error(`At least one cycle exists in this graph. Number of nodes without a root: ${unusedNodesCounter}`)
  }

  return output
}

function bubbleUpChildren(
  currentNode: NodeContainer, 
  nodeMap: Map<string, NodeContainer>, 
  parentChildMap: Map<string, string[]>
) {
  let parentId = currentNode.node.parent_id
  let nodeId = currentNode.node.id

  let isRootNode = !parentId
  let isLeafNode = !parentChildMap.get(nodeId)
  let allChildrenUpdated = isLeafNode || (nodeMap.get(nodeId).children.length === parentChildMap.get(nodeId).length)

  while (!isRootNode && allChildrenUpdated) {
    nodeMap.get(parentId).children.push(currentNode)

    currentNode = nodeMap.get(parentId)
    parentId = currentNode.node.parent_id

    const nodeId = currentNode.node.id
    isRootNode = !parentId
    isLeafNode = !parentChildMap.get(nodeId)
    allChildrenUpdated = nodeMap.get(nodeId).children.length === parentChildMap.get(nodeId).length
  }
}

function createNode({ id, parent_id }: Partial<Node>): Node {
  return {
    id: id ? id : null,
    parent_id: parent_id ? parent_id : null
  }
}

function createNodeContainer(node: Node): NodeContainer {
  return {
    node,
    children: []
  }
}


const defaultInput = [
  {
    id: 'e',
    parent_id: 'd',
  },
  {
    id: 'a',
    parent_id: null,
  },
  {
    id: 'b',
    parent_id: null,
  },
  {
    id: 'c',
    parent_id: null,
  },
  {
    id: 'd',
    parent_id: 'a',
  },
  {
    id: 'f',
    parent_id: 'e',
  },
  {
    id: 'g',
    parent_id: 'b',
  },
]


const input_invalidNodeError = [
  {
    id: 'e',
    parent_id: 'e',
  }
]

const input_cycleDetectedError = [
  {
    id: 'e',
    parent_id: 'a',
  },
  {
    id: 'a',
    parent_id: 'e',
  }
]

console.log('Default input: ', unnormalizeNodes(defaultInput))
console.log('Invalid node error: ', unnormalizeNodes(input_invalidNodeError))
console.log('Cycle detected error: ', unnormalizeNodes(input_cycleDetectedError))