[JS] Nodes in a Subtree

nodesInSubTree.js

function Node(val, children) {
  this.val = val === undefined ? 0 : val;
  this.children = children === undefined ? [] : children;
};

// BFS
function  getNOfDescendants(rootNode, targetVal, startNodeIdx, string) {
  let nOfDescendants = 0;
  const queue = [[rootNode, startNodeIdx === rootNode.val]];

  while(queue.length) {
      const [node, shouldConsider] = queue.shift();
                 
      const idx = node.val;
      if(shouldConsider && string[idx - 1] === targetVal) nOfDescendants++;
      node.children.forEach(child => {
          queue.push([child, shouldConsider || startNodeIdx === child.val]);  
      })
  }
  return nOfDescendants;
}

// DFS
function  getNOfDescendants(node, targetVal, startNodeIdx, string, shouldConsider = false) {
  let nOfDescendants = 0;
  shouldConsider = shouldConsider || startNodeIdx === node.val;
  if(shouldConsider && string[node.val - 1] === targetVal) nOfDescendants++;
  
  for(const child of node.children) {
    nOfDescendants += getNOfDescendants(child, targetVal, startNodeIdx, string, shouldConsider || startNodeIdx === child.val);
  }
  return nOfDescendants;
}


function countOfNodes(root, queries, string) {
  const result = [];
  
  queries.forEach(([startNodeIdx, char]) => {
    result.push(getNOfDescendants(root, char, startNodeIdx, string))    
  });
  
  return result;
}


// SOlution O(|N| + |q|)
// {
//   1: {
//     a: 2,
//     b: 1,  
//   }
//   2: {
//     b: 1
//   }
//   3 : {
//     a: 1
//   }  
// }
function getStringMap(root, string, map = {}) {
  if(!map[root.val]) map[root.val] = {};
  
  root.children.forEach(child =>  {
    getStringMap(child, string, map);
    combineMaps(map[root.val], map[child.val]);
  })
  
  increaseMapPos(map[root.val], string[root.val - 1]);
  return map;
}

function  combineMaps(baseMap, newMap) {
  Object.keys(newMap).forEach(char => {
    increaseMapPos(baseMap, char, newMap[char]);
  });  
}
  
function increaseMapPos(map, pos, amount = 1) {
  if(map[pos]) map[pos] += amount;
  else map[pos] = amount;
}
  
function countOfNodes(root, queries, string) {
  const result = [];  
  const stringMap = getStringMap(root, string);

  queries.forEach(([startNodeIdx, char]) => {
    let count = 0;
    if(stringMap[startNodeIdx] && stringMap[startNodeIdx][char]) count = stringMap[startNodeIdx][char];
    result.push(count);     
  });
  return result;
}