# 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:

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

const [x, xs] = root;
yield x;

for (let i = 0; i < xs.length; i++)
yield* serialize(xs[i]);

yield ")";
}

const Node = (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")));

console.log(
Array.from(serialize(tree)).join("")); // abe)fk)))c)dg)h)i)j)))``````

Apparently, it works but isn't stack safe for very deep trees. How can I transform it into its iterative counterpart?

I know that I need a stack for this. But I cant figure out the details. I'm in particular interested in the underlying mechanics of such a transformation.

I managed to create an iterative pre-order traversal, but oddly enough this didn't help with serializing it iteratively:

``````const Node = (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();

for (let i = xs.length - 1; i >= 0; i--)
stack.push(xs[i]);

yield x;
}
}

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

On Best Solutions

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

``````const Node = (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(""));``````

On

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

``````  const Node = (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:

``````function serialize(node) {
let result = node.value;
while(node) {
// Deep first
while(node.children[0]) {
node = node.children[0];
result += node.value;
}

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

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

``````function s(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
}

const
node = (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);``````