Iterative tree serialization function

Asked by At

Here is a visual representation of the tree I'm working with and the desired string serialization:

enter image description here

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

3 Answers

2
georg 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(""));

0
Jonas Wilms 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;
 }
1
Nina Scholz 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);