Serialize and deserialize binary tree

#1

I was wondering how to serialize and deserialize a binary tree efficiently. This is what I currently have

type binary_tree('a) =
  | Leaf
  | Node('a, binary_tree('a), binary_tree('a));

type str_binary_tree = binary_tree(string);

let node: str_binary_tree =
  Node("12", Node("11", Leaf, Leaf), Node("14", Leaf, Leaf));

let serialize = (node: str_binary_tree): string => {
  let rec aux = (n, acc) =>
    switch (n) {
    | Leaf => acc ++ "-1"
    | Node(x, l, Leaf) => aux(l, acc ++ " " ++ x ++ " " ++ "-1 ")
    | Node(x, Leaf, r) => aux(r, acc ++ " " ++ "-1" ++ " " ++ x)
    | Node(x, l, r) => aux(l, acc ++ x) ++ aux(r, acc)
    };

  aux(node, "");
};

let splitString = str => Js.String.split(" ", str);

Js.log(splitString(serialize(node)));

let rec deserialize = lst => {
  switch (lst) {
  | [] => Leaf
  | [x, ...xs] =>
    x === "-1" ? deserialize(xs) : Node(x, deserialize(xs), deserialize(xs))
  };
};

Js.log(splitString(serialize(node)) |> Array.to_list |> deserialize);

The serialization seems to work, but the deserialization isn’t working as I expect, what changes do I need to make for this to work ?
Thanks

#2

Hi @Tevinthuku,

I found out your question interesting and based on this video: https://www.youtube.com/watch?v=suj1ro8TIVY I have been able to implement a diserialize/serialize tree function. Here’s the code:

type binary_tree('a) =
  | Leaf
  | Node('a, binary_tree('a), binary_tree('a));

type str_binary_tree = binary_tree(string);

let tree: str_binary_tree =
  Node("12", Node("11", Leaf, Leaf), Node("14", Leaf, Leaf));

let serialize = tree => {
  let rec aux = node => {
    switch (node) {
    | Leaf => "-1"
    | Node(s, l, r) => s ++ " " ++ aux(l) ++ " " ++ aux(r)
    };
  };
  aux(tree);
};

let deserialize = serializedTree => {
  let rec aux = nodesLeft => {
    let valueForNode = Belt.MutableQueue.pop(nodesLeft);
    switch (valueForNode) {
    | None
    | Some("-1") => Leaf
    | Some(v) => Node(v, aux(nodesLeft), aux(nodesLeft))
    };
  };
  let arr = Js.String2.split(serializedTree, " ");
  let queue = Belt.MutableQueue.fromArray(arr);
  aux(queue);
};

let serializedResult = serialize(tree);
let deserializedResult = deserialize(serializedResult);

Js.log(serializedResult);
Js.log(deserializedResult);

Hope it will help :slight_smile: