Maximum Genetic Difference Query LeetCode solution in JavaScript

1
class Trie {
2
  constructor() {
3
    this.T = [-1, -1];
4
  }
5
  insert(val) {
6
    let cur = this.T,
7
      firstchangeNode = null,
8
      fcIndex = null;
9
    for (let i = 17; i >= 0; i--) {
10
      // a node can be up to (1e5), whose log2 is 17, so at most we need 17 bits
11
      let next = Number(Boolean(val & (1 << i)));
12
      if (cur[next] === -1) {
13
        if (firstchangeNode === null) (firstchangeNode = cur), (fcIndex = next);
14
        cur[next] = [-1, -1];
15
      }
16
      cur = cur[next];
17
    }
18
    // memorize the first change (if any) that was made during the insertion of val
19
    return [firstchangeNode, fcIndex];
20
  }
21
  search(val) {
22
    let cur = this.T,
23
      res = 0;
24
    for (let i = 17; i >= 0; i--) {
25
      let xor = 1 ^ Number(Boolean(val & (1 << i)));
26
      if (cur[xor] !== -1) (cur = cur[xor]), (res |= 1 << i);
27
      else cur = cur[xor ^ 1];
28
    }
29
    return res;
30
  }
31
}
32
var maxGeneticDifference = function (parents, queries) {
33
  let root,
34
    n = parents.length,
35
    res = [...Array(n)].map((d) => {}),
36
    Q = [...Array(n)].map((d) => []),
37
    adj = [...Array(n)].map((d) => []);
38
  // create some objects for fast access to the results
39
  for (let [node, val] of queries)
40
    Q[node].push(val), (res[node] = {}), (res[node][val] = undefined);
41
  // create an adjacency list that points to the next node
42
  for (let i = 0; i < parents.length; i++)
43
    if (parents[i] !== -1) adj[parents[i]].push(i);
44
    else root = i;
45
  let T = new Trie();
46
  //traverse the tree
47
  let dfs = (node) => {
48
    let [fnode, index] = T.insert(node); //insert the value of a node to our trie
49
    for (let q of Q[node]) //answer all the queries for our current node
50
      res[node][q] = T.search(q);
51
    for (let nei of adj[node]) // dfs to the children nodes
52
      dfs(nei);
53
    if (fnode !== null)
54
      // if my trie was altered during this turn, revert the change
55
      fnode[index] = -1;
56
  };
57
  dfs(root);
58
  //return the results, which have already been calculated
59
  return queries.map(([node, val]) => res[node][val]);
60
};