Hard Trees
Serialize / Deserialize Binary Tree
Receives an array of integers and builds a binary search tree from them (duplicates ignored), exactly like the Binary Search Tree exercise. It then serializes that tree into a single string by walking it in preorder — the node itself first, then its left subtree, then its right — writing each node's value as a token and a "#" token wherever a child is missing, so the tree's exact shape survives the trip. It parses that same string back into a brand-new tree by consuming the tokens in the same preorder sequence, then reads the rebuilt tree back out in preorder. Returns that final preorder array, which — if serialization and deserialization are correct — is identical to the preorder of the tree that was originally built.
Visualization
- Input
- Result
Algorithm code
// Serialize / Deserialize Binary Tree — a single pure function. Builds a
// binary search tree from the given values (duplicates ignored), serializes
// it to a preorder string with "#" marking empty children, deserializes that
// same string back into a tree, and returns the rebuilt tree's preorder
// traversal — proving the round trip reconstructs the exact same shape.
const NULL_TOKEN = "#";
/**
* @param {number[]} values - values to insert, in order
* @returns {number[]} preorder traversal of the tree rebuilt from the serialized string
*/
export function serializeDeserializeTree(values) {
const insert = (node, value) => {
if (node === null) {
return { value, left: null, right: null };
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
}
return node;
};
let root = null;
for (const value of values) {
root = insert(root, value);
}
const serialize = (node, tokens) => {
if (node === null) {
tokens.push(NULL_TOKEN);
return;
}
tokens.push(String(node.value));
serialize(node.left, tokens);
serialize(node.right, tokens);
};
const tokens = [];
serialize(root, tokens);
const data = tokens.join(",");
const deserialize = (encoded) => {
const parts = encoded.split(",");
let index = 0;
const build = () => {
const token = parts[index];
index += 1;
if (token === NULL_TOKEN) {
return null;
}
const node = { value: Number(token), left: null, right: null };
node.left = build();
node.right = build();
return node;
};
return build();
};
const rebuilt = deserialize(data);
const preorder = (node, out) => {
if (node === null) {
return;
}
out.push(node.value);
preorder(node.left, out);
preorder(node.right, out);
};
const out = [];
preorder(rebuilt, out);
return out;
}FUNCTION serializeDeserializeTree(values)
root ← NULL
FOR EACH value IN values
root ← INSERT(root, value)
END FOR
tokens ← []
SERIALIZE(root, tokens)
data ← JOIN(tokens, ",")
rebuilt ← DESERIALIZE(data)
out ← []
PREORDER(rebuilt, out)
RETURN out
END FUNCTION
FUNCTION INSERT(node, value)
IF node IS NULL
RETURN { value: value, left: NULL, right: NULL }
END IF
IF value < node.value
node.left ← INSERT(node.left, value)
ELSE IF value > node.value
node.right ← INSERT(node.right, value)
END IF
RETURN node
END FUNCTION
FUNCTION SERIALIZE(node, tokens)
IF node IS NULL
APPEND "#" TO tokens
RETURN
END IF
APPEND TO_STRING(node.value) TO tokens
SERIALIZE(node.left, tokens)
SERIALIZE(node.right, tokens)
END FUNCTION
FUNCTION DESERIALIZE(encoded)
parts ← SPLIT(encoded, ",")
cursor ← { index: 0 }
RETURN BUILD(parts, cursor)
END FUNCTION
FUNCTION BUILD(parts, cursor)
token ← parts[cursor.index]
cursor.index ← cursor.index + 1
IF token = "#"
RETURN NULL
END IF
node ← { value: TO_NUMBER(token), left: NULL, right: NULL }
node.left ← BUILD(parts, cursor)
node.right ← BUILD(parts, cursor)
RETURN node
END FUNCTION
FUNCTION PREORDER(node, out)
IF node IS NULL
RETURN
END IF
APPEND node.value TO out
PREORDER(node.left, out)
PREORDER(node.right, out)
END FUNCTION