tail-call recursive binary tree inverter

invert.js

function invert(tree, toInvR = [], path = [], res = null) {
  // tree == nodo corrente
  // path[path.length - 1] == nodo padre

  if (!tree) {
    return null;
  }

  const parent = path[path.length - 1]; // is undefined iif res === null
  const newNode = Node(tree.value);

  if (parent) {
    // inversione
    if (parent.direction === 'right') parent.newParent.left = newNode;
    else if (parent.direction === 'left') parent.newParent.right = newNode;
  }

  if (!!tree.left) {
    return invert(
      tree.left,
      [tree.right, ...toInvR],
      [...path, { parent: tree, newParent: newNode, direction: 'left' }]
    );
  } else if (!!tree.right) {
    return invert(
      tree.right,
      [...toInvR],
      [...path, { parent: tree, newParent: newNode, direction: 'right' }]
    );
  } else if (toInvR.length > 0) {
    const [nextHop, ...restToInvR] = toInvR;
    const pathClone = [...path];

    while (pathClone[pathClone.length - 1].parent.right != nextHop)
      pathClone.pop();

    // sicuramente stava a dx del parent
    // dato che diamo precedenza ai figli a sx
    pathClone[pathClone.length - 1].direction = 'right';

    return invert(nextHop, restToInvR, pathClone);
  } else return path[0].newParent; // trovo sicuramente il nodo radice in path[0]
}

function Node(value = null, left = null, right = null) {
  return { value, left, right };
}

const tree1 = Node(
  1,
  Node(2, Node(3, Node(4), Node(5)), Node(6, Node(7), Node(8))),
  Node(9, Node(10, Node(11), Node(12)), Node(13, Node(14), Node(15)))
);

const tree2 = Node(
  1,
  Node(2, null, Node(6, Node(7), Node(8))),
  Node(9, null, Node(13, Node(14), Node(15)))
);

console.log(tree1);
console.log(invert(tree1));

invertInPlace.js

function invert(tree, toInv = []) {
  
  if(tree) {
    [tree.left, tree.right] = [tree.right, tree.left]
  }
  
  const newToInv = toInv.concat([tree.left, tree.right].filter(Boolean))
  
  if(newToInv.length > 0) {
    const [next, ...rest] = newToInv
    return invert(next, rest)
  }
  
}

function Node(value = null, left = null, right = null) {
  return { value, left, right };
}

const tree1 = Node(
  1,
  Node(2, Node(3, Node(4), Node(5)), Node(6, Node(7), Node(8))),
  Node(9, Node(10, Node(11), Node(12)), Node(13, Node(14), Node(15)))
);

const tree2 = Node(
  1,
  Node(2, null, Node(6, Node(7), Node(8))),
  Node(9, null, Node(13, Node(14), Node(15)))
);

console.log(tree1);
invert(tree1)
console.log(tree1);