Refactor Code to Tail-Recursion

Question

I have a function that goes through "nodes" that have a key and their own nodes array. I also have an array of allowed keys. The goal is simple: If a node has an allowed key, or a child that has an allowed key, keep it, otherwise, remove it. The current solution looks like this:

var allowedKeys = ['x', 'y', 'z'];

var nodes = [{
    key: 'x',
    nodes: []
  },
  {
    key: 'b',
    nodes: [{
        key: 'y',
        nodes: []
      },
      {
        key: 'lol',
        nodes: []
      },
    ]
  },
  {
    key: 'c'
  },
  {
    key: 'd',
    nodes: []
  },
  {
    key: 'e',
    nodes: [{
        key: 't',
        nodes: [{
          key: 'z',
          nodes: []
        }]
      },
      {
        key: 'r',
        nodes: []
      },
    ]
  },
  {
    key: 'f',
    nodes: []
  }

];

function hasChildNodes(node) {
  var hasChildNodes = node.hasOwnProperty('nodes') && node.nodes.length > 0;
  return hasChildNodes;
}

function removeUnnecessaryNodes(nodes, allowedKeys) {
  nodes.forEach(node => {
    if (hasChildNodes(node)) {
      node.nodes = removeUnnecessaryNodes(node.nodes, allowedKeys);
    }
  });

  nodes = nodes.filter(node => allowedKeys.includes(node.key) || hasChildNodes(node));

  return nodes;
}


var filteredNodes = removeUnnecessaryNodes(nodes, allowedKeys);
console.log(filteredNodes);

I would like to refactor this to use tail-recursion to avoid blowing up the stack. I am starting to feel like it isn't possible.

P.S. I realize most javascript implementations don't use tail-recursion optimization, humor me.

Answer 1

Following up on my comment, I wanted to try a stack version. It's not nearly as clean as I'd hoped, but I figured I'd post it anyway in the hopes that it sheds light in some capacity.

var nodes = [{
    key: 'x',
    nodes: []
  },
  {
    key: 'b',
    nodes: [{
        key: 'y',
        nodes: []
      },
      {
        key: 'lol',
        nodes: []
      },
    ]
  },
  {
    key: 'c'
  },
  {
    key: 'd',
    nodes: []
  },
  {
    key: 'e',
    nodes: [{
        key: 't',
        nodes: [{
          key: 'z',
          nodes: []
        }]
      },
      {
        key: 'r',
        nodes: []
      },
    ]
  },
  {
    key: 'f',
    nodes: []
  }
];

var allowedKeys = ['x', 'y', 'z'];

const removeUnnecessaryNodes = (nodes, allowedKeys) => {
  const allowed = new Set(allowedKeys);
  const root = {nodes: nodes};
  const stack = [root];
  
  while (stack.length) {
    let curr = stack.pop();
    
    if (curr.nodes && curr.nodes.length) {

      // non-empty node, push children on stack
      curr.nodes.forEach(e => {
        e.parent = curr;
      	stack.push(e);
      });
    }
    else if (!allowed.has(curr.key)) {

      // this is a disallowed leaf; remove it
      let p = curr.parent;

      if (p) {
        p.nodes = p.nodes.filter(e => e !== curr); // O(n)
      }

      // move up the structure, pruning dead ancestors
      while (p && !p.nodes.length && !allowed.has(p.key)) {
        curr = p;
        p = curr.parent;

        if (p) {
          p.nodes = p.nodes.filter(e => e !== curr); // O(n)
        }
      }
    }
  }

  // clean up temporary parent keys
  stack.push(root);
  
  while (stack.length) {
    const curr = stack.pop();
    
    if (curr.nodes) {
      curr.nodes.forEach(e => {
        delete e.parent;
      	stack.push(e);
      });
    }
  }
  
  return root.nodes;
};

var filteredNodes = removeUnnecessaryNodes(nodes, allowedKeys);
console.log(JSON.stringify(filteredNodes, null, 4));

Explanation

Preparation involves adding a nodes key to the outer array and converting allowedKeys to a set for fast lookups. Then, DFS the structure, assigning new parent properties to each key and pushing children onto a stack. If a leaf node is reached and its key is disallowed, unlink it from its parent node list. If the parent list is then made empty and the parent node's key is disallowed, unlink that as well and repeat until a valid ancestor is reached. Finally, perform another DFS on the structure to remove the temporary parent property.

Areas of improvement

I tried to use an object to store parent properties but ran into comparison/duplication problems and resorted to the linked list approach. I'm sure that can be resolved, saving the second cleanup DFS and potential key conflicts.

Also, the node list filtering process is O(n) and could be improved with a hash or at least an early bailout once the child key is found.

I'm sure there are others! I'd be curious to hear feedback or hear how this performs on a large input.