Calculate tree node changes

Saw an interesting interview questions from DoorDash at Leetcode's forum:

"At DoorDash, menus are updated daily even hourly to keep them up-to-date. Each menu can be regarded as a tree. A menu can have many categories; each category can have many menu_items; each menu_item can have many item_extras; An item_extra can have many item_extra_options…"

class Node {
    String key;
    int value;
    boolean active;
    List<Node> children;
}

"We will compare the new menu sent from the merchant with our existing menu. Each item can be considered as a node in the tree. The definition of a node is defined above. Either value change or the active status change means the node has been changed. There are times when the new menu tree structure is different from existing trees, which means some nodes are set to null. In this case, we only do soft delete for any nodes in the menu. If that node or its sub-children are null, we will treat them ALL as inactive. There are no duplicate nodes with the same key.

Return the number of changed nodes in the tree."

        Existing tree
         a(1, T)
        /       \
     b(2, T)   c(3, T)
    /     \           \
d(4, T) e(5, T)   f(6, T)

        New tree 
        a(1, T)
            \
           c(3, F)
               \
               f(66, T)

"a(1, T) a is the key, 1 is the value, T is True for active status
For example, there are a total of 5 changed nodes. Node b, Node d, Node e are automatically set to inactive. The active status of Node c and the value of Node f changed as well."

      Existing tree
        a(1, T)
      /         \
    b(2, T)   c(3, T)
  /       \           \
d(4, T) e(5, T)      g(7, T)

            New tree
            a(1, T)
          /        \
   b(2, T)         c(3, T)
   /    |    \           \
d(4, T) e(5, T) f(6, T)    g(7, F) 

(https://leetcode.com/discuss/interview-question/1367130/doordash-phone-interview)

There's also a simplified version removing the activate status:

class Node {
   String key;
   int value;
   List<Node> children;
}

An example would be:

// Existing Menu in our system:

         Existing tree
             a(1)
           /       \
         b(2)      c(3)
       /       \       \
   d(4)      e(5)      g(7)    
// New Menu sent by the Merchant:

             New tree
               a(1)
           /          \    
        b(2)         h(8)  
     /    |   \           \    
  e(5)   d(4)   f(6)       g(7) 

"Expected Answer: 5 Explanation: There are a total of 5 changed nodes. Node f is a newly-added node. c(3) and old g(7) are deactivated; h(8) and new g(7) are newly added nodes" (https://leetcode.com/discuss/interview-question/1265810/Doordash-PhoneScreen)

To safe some time, I only tried the simplified version a bit. The key point to this problem is to identify how the difference is calculated. Let's use the above example. The difference from two trees is 5 but not 2. It means it's not simply comparing all the nodes and returning different nodes. The node key also plays an important role here. If the keys are the same, it means the value change only, but if the keys are different, it means a totally different subtree. After figuring this out, we can just start coding it out now (using TypeScript of course):

/**
 * calculate total sub nodes from a Node
 */
function totalNodes(node: TreeNode): number {
  let result = 0;
  const nodes: TreeNode[] = [];
  if (!node) {
      return 0;
  }
  nodes.push(node);
  while(nodes.length > 0) {
      const currentNode = nodes.pop()!;
      ++result;
      nodes.push(...currentNode.children);
  }
  return result;
}

function calculate(nodeA: TreeNode, nodeB: TreeNode, result: number): number {
  if (!nodeA && !nodeB) {
      return result;
  }
  if (!nodeA) {
      return result + totalNodes(nodeB);
  }
  if (!nodeB) {
      return result + totalNodes(nodeA);
  }
  if (nodeA.key !== nodeB.key) {
      return result + totalNodes(nodeA) + totalNodes(nodeB);
  }
  if (nodeA.value !== nodeB.value) {
      ++result;
  }
  
  const visited: string[] = [];
  const keysInNodeBChildren: Map<string, number> = new Map();
  nodeB.children.forEach((node, index) => keysInNodeBChildren.set(node.key, index));
  
  for (const node of nodeA.children) {
      if (keysInNodeBChildren.has(node.key)) {
          result += calculate(node, nodeB.children[keysInNodeBChildren.get(node.key)!], 0);
          visited.push(node.key);
      } else {
          result += totalNodes(node);
      }
      console.log(result);
  }
  for (const node of nodeB.children) {
      if (visited.indexOf(node.key) !== -1) {
          result += totalNodes(node);
      }
  }
  return result;
}

function calculateChanges(existingTree: TreeNode, newTree: TreeNode): number {
  return calculate(existingTree, newTree, 0);
}

(well, side note.. I really need to figure out how to pretty print code in Ghost)