Find the highest object in array tree of nested children

I have an array of nested regions that look like this:

Egypt
- Zone 1
  - Tagamo3
  - Giza
  - Helwan
  - Fayoum
- Zone 2
  - Gesr ElSuis
    - test
  - Delta
  - Mohandeseen
  - Down Town

The array itself:

[
  {
    "key": 10,
    "title": "Egypt",
    "parent_key": null,
    "children": [
      {
        "key": 1,
        "title": "Zone 1",
        "parent_key": 10,
        "children": [
          {
            "key": 3,
            "title": "Tagamo3",
            "parent_key": 1,
            "children": []
          },
          {
            "key": 7,
            "title": "Giza",
            "parent_key": 1,
            "children": []
          },
          {
            "key": 8,
            "title": "Helwan",
            "parent_key": 1,
            "children": []
          },
          {
            "key": 11,
            "title": "Fayoum",
            "parent_key": 1,
            "children": []
          }
        ]
      },
      {
        "key": 2,
        "title": "Zone 2",
        "parent_key": 10,
        "children": [
          {
            "key": 4,
            "title": "Gesr ElSuis",
            "parent_key": 2,
            "children": [
              {
                "key": 12,
                "title": "test",
                "parent_key": 4,
                "children": []
              }
            ]
          },
          {
            "key": 5,
            "title": "Delta",
            "parent_key": 2,
            "children": []
          },
          {
            "key": 6,
            "title": "Mohandeseen",
            "parent_key": 2,
            "children": []
          },
          {
            "key": 9,
            "title": "Down Town",
            "parent_key": 2,
            "children": []
          }
        ]
      }
    ]
  }
]

I want to return to the highest region in a given input

Examples:

input [7, 1, 10] should return [10] since 10 is Egypt parent of 1 and 7
input [1, 2] should return both [1, 2] since they are on the same level both Zone 1 and zone 2 located under Egypt
input [2, 3, 1] should return [2, 1] since they are on the same level and 3 removed because it's a child of 1
input [1, 4] should return [1, 4] since they are on different levels and no one parent to the other

Solution

First it helps to turn your tree structure into a map of descendant ids, recursively:

const descendantsMap = new Map<number, Set<number>>();
function walk(tree: Tree) {
  const s: Set<number> = new Set();
  descendantsMap.set(tree.key, s);
  for (const t of tree.children) {
    walk(t);
    s.add(t.key);
    descendantsMap.get(t.key)?.forEach(v => s.add(v));
  }
}
arr.forEach(walk);

We are building up a Map from each key in your tree structure to a Set of the keys of its descendants. The walk() function is recursive, and we merge the descendants for the children of each node into the descendants for the current node.

Let's make sure it looks right:

console.log(descendantsMap);
/* Map (12) {
    10 => Set (11) {1, 3, 7, 8, 11, 2, 4, 12, 5, 6, 9}, 
    1 => Set (4) {3, 7, 8, 11}, 
    3 => Set (0) {}, 
    7 => Set (0) {}, 
    8 => Set (0) {}, 
    11 => Set (0) {}, 
    2 => Set (5) {4, 12, 5, 6, 9}, 
    4 => Set (1) {12}, 
    12 => Set (0) {}, 
    5 => Set (0) {}, 
    6 => Set (0) {}, 
    9 => Set (0) {}
} */

Yes. You can see how now we have a quick mapping from each key to the set of keys in its descendant subtree.

Now to get the "highest" entries in an array (I would call these the "shallowest" since they are closest to the root), we find all the descendants of all the elements in the array and then filter these out of the array:

const shallowest = (x: number[]): number[] => {
  const descendants = new Set<number>();
  for (const v of x) {
    descendantsMap.get(v)?.forEach(i => descendants.add(i));
  }
  console.log(descendants); // just to understand what's happening
  return x.filter(v => !descendants.has(v));
}

Let's test it:

console.log(shallowest([7, 1, 10])); 
// descendants are {3, 7, 8, 11, 1, 2, 4, 12, 5, 6, 9} 
// output [10]

console.log(shallowest([1, 2])); 
// descendants are {3, 7, 8, 11, 4, 12, 5, 6, 9};
// output [1, 2]

console.log(shallowest([2, 3, 1])); 
// descendants are {4, 12, 5, 6, 9, 3, 7, 8, 11};
// output [2, 1]

console.log(shallowest([1, 4])); 
// descendants are {3, 7, 8, 11, 12};
// output [1, 4]

Looks good. You can see that shallowest([7, 1, 10]) first finds all the descendants of 7, 1, and 10, which is {3, 7, 8, 11, 1, 2, 4, 12, 5, 6, 9}, or everything except 10. So when we filter those out of [7, 1, 10] we are left with just 10. Similarly, shallowest([1, 2]) and shallowest([1, 4]) produce sets of descendants that don't overlap at all with the input, so the output is identical to the input. And with shallowest([2, 3, 1]), the list of descendants contains 3 but not 2 or 1, so the output is [2, 1].

Playground link to code