I've come across this problem before, say with Categories or Tags. You have multiple tags that can be children of each other:

{ id: 1, name: 'Sports', parent_id: null }
{ id: 2, name: 'Fruits', parent_id: null }
{ id: 3, name: 'Citrus', parent_id: 2 }
{ id: 4, name: 'Orange', parent_id: 3 }
{ id: 5, name: 'Hockey', parent_id: 1 }

Another representation of these nodes:

Sports -> Hockey
Fruits -> Citrius -> Orange

What is the algorithm that efficiently finds the top-most parent for each node? So we can go from Orange -> Fruits in O(1) time.

(Requires some preprocessing).

CodePudding user response：

Preprocessing: parse the tree once storing the depth of each node.

Algorithm: follow parents of the deeper node until both nodes are at the same depth, then follow parents of both in lockstop. While following in lockstep, check for equality. The first instance of equality is the deepest common node.

This runs in O(depth).

CodePudding user response：

Idea:

1. First create a dictionary for each id that takes O(n) where n is the length of categories array.
2. Traverse each array element and look for its top parent so it takes O(n*d) where d is the depth of its parent and build a dictionary that contains keys as child names and values as parent properties.

So the overall dominating factor is O(n*d) for preprocessing.

Improvement:

We can also reduce the computations of getParent() by using Dynamic programming. For example, look at this dependency path Fruits -> Citrius -> Orange so when we visit Citrius we know that ends up in Fruits so we need to memoize the result. so when next time when we start from Orange the next node is Citrius and we know from Citrius we can have the result Fruits. So no need to visit all nodes.

const categories = [
{ id: 1, name: 'Sports', parent_id: null },
{ id: 2, name: 'Fruits', parent_id: null },
{ id: 3, name: 'Citrus', parent_id: 2 },
{ id: 4, name: 'Orange', parent_id: 3 },
{ id: 5, name: 'Hockey', parent_id: 1 },
{ id: 6, name: 'Apple', parent_id: 2 }
];

//Build a dictionary for each id so we can look up its parent efficiently while traversing
const refDict = categories.reduce((acc, item) => ({ ...acc,
  [item.id]: item
}), {});

//it looks for its parent
const getParent = (id) => {
  const child = refDict[id];
  if (child.parent_id === null) return { ...child
  };
  return getParent(child.parent_id);
}

//final dict which contains keys as the name of every child and value as its parent's properties
//So we can look at any topmost parent in constant time
const finalDict = categories.reduce((acc, item) => (item.parent_id === null ? { ...acc
} : { ...acc,
  [item.name]: getParent(item.id)
}), {});

console.log(finalDict);
console.log("parent - ", finalDict["Orange"]);

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

Hope it helps!