Serialize
String serialize(Node root) {
StringBuilder sb = new StringBuilder();
helper(root, sb);
return sb.toString();
}
void helper(Node n, StringBuilder sb) {
if (n == null) { sb.append("# "); return; }
sb.append(n.val).append(' ');
helper(n.left, sb); helper(n.right, sb);
}Advertisement
Deserialize
Node deserialize(String data) {
Deque tokens = new ArrayDeque<>(Arrays.asList(data.split(" ")));
return build(tokens);
}
Node build(Deque tokens) {
String t = tokens.pollFirst();
if (t.equals("#")) return null;
Node n = new Node(Integer.parseInt(t));
n.left = build(tokens);
n.right = build(tokens);
return n;
} Advertisement
Level-order variant
BFS with null markers. Different string format, same idea. Level-order is easier for humans to read.
BST-specific optimization
Pre-order alone suffices for BST (invariant reconstructs structure). No null markers needed.