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.