Save a Tree as Text and Load It Back
Solve this ProblemDesign a way to turn a binary tree into text and back. In this exercise your solution must contain both halves — a serialize step that converts the tree to a string, and a deserialize step that builds a brand-new tree from that string — and the function returns the tree obtained after the round trip. You may choose any text format you like, as long as it records the values and the exact shape of the tree, so that the rebuilt tree equals the original.
A level-order text is easy to read but spends a "null" on every missing child slot. A pre-order text with "#" markers can be read back with a simple recursion that mirrors the tree itself.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; −1000 ≤ node.val ≤ 1000; values may repeat - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Inside your solution, write BOTH a serialize step (tree → text) and a deserialize step (text → a brand-new tree). You choose the text format — the only requirement is that it stores the values and the exact shape, and that it uses characters your deserializer can split on (digits, "-", ",", "#" or "null") - ◆
Return the tree obtained by deserializing the text of the given tree. The returned tree must be equal to the given one in shape and values; it is checked as a level-order list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Level Order With "null" Markers
GoodSerialize: walk the tree level by level with a queue that also holds the MISSING children. A real node writes its value and queues both children (which may be missing); a missing child writes "null" and queues nothing. The written tokens, joined by commas, describe every level from left to right. Deserialize: split the text, create the root from the first token, and keep a queue of nodes waiting for children; for each waiting node, read the next two tokens as its left and right child ("null" means no child, anything else becomes a new node that also joins the queue). Both directions touch each token once: O(n) time and O(n) space, but the text contains a "null" for every missing child slot.
O(n)O(n)1class Solution {
2 public TreeNode cloneViaText(TreeNode root) {
3 return decode(encode(root));
4 }
5
6 private String encode(TreeNode root) {
7 StringBuilder sb = new StringBuilder();
8 if (root == null) return "";
9 LinkedList<TreeNode> queue = new LinkedList<>();
10 queue.add(root);
11 while (!queue.isEmpty()) {
12 TreeNode node = queue.poll();
13 if (node == null) {
14 sb.append("null,");
15 continue;
16 }
17 sb.append(node.val).append(",");
18 queue.add(node.left);
19 queue.add(node.right);
20 }
21 return sb.toString();
22 }
23
24 private TreeNode decode(String text) {
25 if (text.isEmpty()) return null;
26 String[] tokens = text.split(",");
27 TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
28 Queue<TreeNode> queue = new ArrayDeque<>();
29 queue.add(root);
30 int i = 1;
31 while (!queue.isEmpty() && i < tokens.length) {
32 TreeNode node = queue.poll();
33 if (!tokens[i].equals("null")) {
34 node.left = new TreeNode(Integer.parseInt(tokens[i]));
35 queue.add(node.left);
36 }
37 i++;
38 if (i < tokens.length && !tokens[i].equals("null")) {
39 node.right = new TreeNode(Integer.parseInt(tokens[i]));
40 queue.add(node.right);
41 }
42 i++;
43 }
44 return root;
45 }
46}Optimal — Pre-Order With "#" Markers, Read Back Recursively
OptimalSerialize with a recursive pre-order walk: write the node's value, then the whole left subtree, then the whole right subtree, and write "#" for every missing child. That text has a unique reading, because the "#" markers make the end of every subtree visible. Deserialize with a mirror-image recursion and one running index into the tokens: read a token; "#" means an empty subtree; otherwise create a node and build its left subtree by reading, then its right subtree by reading. No queue and no bookkeeping of "who is waiting for children" — the recursion structure mirrors the tree, and the text has exactly 2n + 1 tokens. O(n) time and space.
O(n)O(n)1class Solution {
2 private int pos;
3
4 public TreeNode cloneViaText(TreeNode root) {
5 StringBuilder sb = new StringBuilder();
6 write(root, sb);
7 pos = 0;
8 return read(sb.toString().split(","));
9 }
10
11 private void write(TreeNode node, StringBuilder sb) {
12 if (node == null) {
13 sb.append("#,");
14 return;
15 }
16 sb.append(node.val).append(",");
17 write(node.left, sb);
18 write(node.right, sb);
19 }
20
21 private TreeNode read(String[] tokens) {
22 String token = tokens[pos++];
23 if (token.equals("#")) return null;
24 TreeNode node = new TreeNode(Integer.parseInt(token));
25 node.left = read(tokens);
26 node.right = read(tokens);
27 return node;
28 }
29}