Iterative Tree Serialization Function

Here is a visual representation of the tree I'm working with and the desired string serialization: Here is a recursive solution: Apparently, it works but isn't stack safe for ver

Solution 1:

Your serialization basically adds an extra dummy child to each node, so you have to "visit" it when iterating:

constNode = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

function* preOrderIt(root) {
  if (root.length === 0)
    return;

  const stack = [root];

  while (stack.length > 0) {
    let [x, xs] = stack.pop();

    if (x !== ')')             // <-
      stack.push([')', []]);   // <-for (let i = xs.length - 1; i >= 0; i--)
      stack.push(xs[i]);

    yield x;
  }
}



console.log(
  Array.from(preOrderIt(tree)).join(""));

Solution 2:

One option would be to link the nodes. That way you can traverse the tree without keeping the position you are in:

constNode = (value, ...children) => {
   const node = { value, children };
   children.forEach(child => child.parent = node);
   if(children.length > 1) 
      children.reduceRight((curr, prev) => ((prev.next = curr), prev));
   return node;
 };

How does that help? Well:

functionserialize(node) {
  let result = node.value;
  while(node) {
    // Deep firstwhile(node.children[0]) {
      node = node.children[0];
      result += node.value;
    }

    // then rightif(node.next) {
      node = node.next;
      result += ")" + node.value;
    } else {
      // and up at the last nodewhile(node && !node.next) {
        node = node.parent;   
        result += ")";
       }
       result += ")";
       if(node) {
        node = node.next;
        result += node.value;
       }
     }
   }
   return result;
 }

Solution 3:

A different approach by using an array for the levels and iterating deeper levels first.

functions(root) {
    var i = 0,
        node,
        levels = [[root]],
        result = '';

    while (i !== -1) {
        [node, ...levels[i]] = levels[i];
        if (node) {
            result += node[0];
            if (node[1].length) {
                levels[++i] = node[1];
                continue;
            }
        } else {
            i--;
        }
        result += ')';
    }
    return result.slice(0, -1); remove extra bracket for the outer missing array
}

constnode = (x, ...xs) => ([x, xs]),
    tree = node("a", node("b", node("e"), node("f", node("k"))), node("c"), node("d", node("g"), node("h"), node("i"), node("j"))),
    result = s(tree);

console.log(result);