DSA-087 · A complete preorder grammar with explicit null child slots

Serialize and Deserialize Binary Tree

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 27536 deterministic checks. Learner drafts are not executed.

Understand the problem

Serialize a binary tree to one canonical string, and deserialize that format into a fresh independent tree. Preserve ordered shape and int values exactly.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
Canonical grammar is tree := # | int,tree,tree. Tokens are comma-separated with no whitespace. int is exactly Integer.toString(value): no plus, leading zero, -0, Unicode digits or out-of-range values. Empty tree serializes to #; empty string is invalid.
serialize preserves the input graph. deserialize returns fresh node objects and throws IllegalArgumentException for malformed/truncated/trailing/noncanonical data or more than 100,000 nonnull nodes; null text throws NullPointerException. It exposes no partially built tree on failure. The recursive Baseline is only for shallow input/text; public iterative methods support full depth.

Examples

Input: tree=[1,2,3,null,4]
Output: 1,2,#,4,#,#,3,#,#
Null markers distinguish a missing left child from a missing right child.
Input: tree=[]
Output: text=#; decoded root=null
Null has one complete grammar token.
Input: text=1,#
Output: IllegalArgumentException
The root still needs its right-child token.

Before you start

Preorder traversal and explicit null positions
Iterative pending child slots and canonical input parsing

Recognize the structure

Values without null positions do not uniquely determine shape. A binary node owns two ordered child slots; preorder emits the node then a complete left tree and a complete right tree. Null closes exactly one slot.

Try before revealing

Hint 1

How will you distinguish the two sides of a missing child?

Hint 2

A value token consumes one slot and creates two ordered child slots; # only consumes one.

Hint 3

Use a preorder wrapper stack to write and a left/right slot stack to read, then check exact completion.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Recursive grammar writer and reader

Write node value then recursively write left and right, writing # for null. Reading consumes one token and recursively fills both child subtrees for each value token. For 1,#,#, root 1 owns two slots and both # tokens close them. A final cursor check rejects trailing data. The iterative version represents these suspended grammar calls explicitly.

Improve the baseline

Serialize nullable work through wrappers

Push Item(root); pop one item, append its canonical value or #, and for nonnull nodes push right then left. A wrapper permits a null field without a null ArrayDeque entry.

Deserialize into pending slots

Parse the root, then keep Slot(node,next) frames. The next token fills the top frame’s left or right field. Pop a parent after assigning its right slot; a nonnull child pushes its own two-slot continuation on top.

Validate tokens and complete consumption

Integer.parseInt alone accepts noncanonical forms, so require Integer.toString(parsed).equals(token). Reject a token when no slots remain, an unfinished stack at end, and node count above the limit. Root # must be the only token.

Why it is correct

Unique grammar decomposition

Each tree begins with one token. # determines an empty tree; a value token is followed by exactly one complete left and right grammar tree. Null positions make this decomposition unambiguous.

Pending-slot invariant

The stack top is the next unfilled preorder child slot. Assigning a child consumes one slot; a nonnull child adds its two slots before older right-side work. Popping a completed parent does not lose the still-live child reference.

Round trip and rejection

Writing emits exactly the grammar that reading reconstructs, preserving each value and edge position while allocating fresh nodes. Missing/trailing tokens violate slot completion; canonical checks ensure reserialization returns the identical accepted string.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    private record Item(Node node) {}
    private static final class Slot {
        final Node node;
        int next;
        Slot(Node node) { this.node = node; }
    }
    private static Node token(String text) {
        if (text.equals("#")) return null;
        try {
            int value = Integer.parseInt(text);
            if (!Integer.toString(value).equals(text)) throw new IllegalArgumentException("noncanonical integer");
            return new Node(value);
        } catch (NumberFormatException exception) { throw new IllegalArgumentException("invalid token",exception); }
    }
    public static String serialize(Node root) {
        StringBuilder text = new StringBuilder();
        ArrayDeque<Item> stack = new ArrayDeque<>();
        stack.push(new Item(root));
        while (!stack.isEmpty()) {
            Node node = stack.pop().node;
            if (text.length() > 0) text.append(',');
            if (node == null) text.append('#');
            else {
                text.append(node.value);
                stack.push(new Item(node.right)); stack.push(new Item(node.left));
            }
        }
        return text.toString();
    }
    public static Node deserialize(String text) {
        Objects.requireNonNull(text,"text");
        String[] tokens = text.split(",",-1);
        Node root = token(tokens[0]);
        if (root == null) {
            if (tokens.length != 1) throw new IllegalArgumentException("trailing tokens");
            return null;
        }
        int count = 1;
        ArrayDeque<Slot> stack = new ArrayDeque<>(); stack.push(new Slot(root));
        for (int i = 1; i < tokens.length; i++) {
            if (stack.isEmpty()) throw new IllegalArgumentException("trailing tokens");
            Slot parent = stack.peek();
            Node child = token(tokens[i]);
            if (child != null && ++count > 100000) throw new IllegalArgumentException("too many nodes");
            if (parent.next == 0) { parent.node.left = child; parent.next = 1; }
            else { parent.node.right = child; stack.pop(); }
            if (child != null) stack.push(new Slot(child));
        }
        if (!stack.isEmpty()) throw new IllegalArgumentException("missing child token");
        return root;
    }
    public static final class Baseline {
        private static void write(Node node, StringBuilder text) {
            if (text.length() > 0) text.append(',');
            if (node == null) text.append('#');
            else { text.append(node.value); write(node.left,text); write(node.right,text); }
        }
        public static String serialize(Node root) { StringBuilder text = new StringBuilder(); write(root,text); return text.toString(); }
        private static Node read(String[] tokens, int[] cursor) {
            if (cursor[0] == tokens.length) throw new IllegalArgumentException("missing token");
            Node node = token(tokens[cursor[0]++]);
            if (node != null) {
                if (++cursor[1] > 100000) throw new IllegalArgumentException("too many nodes");
                node.left = read(tokens,cursor); node.right = read(tokens,cursor);
            }
            return node;
        }
        public static Node deserialize(String text) {
            Objects.requireNonNull(text,"text"); String[] tokens = text.split(",",-1); int[] cursor = {0,0};
            Node root = read(tokens,cursor);
            if (cursor[0] != tokens.length) throw new IllegalArgumentException("trailing tokens");
            return root;
        }
    }
}

Read the meaningful blocks

Do not trim or normalize malformed text

The API deliberately rejects whitespace, +1, 01 and -0 rather than silently accepting multiple encodings.

Keep null tokens in serialization

A tree with n nodes has n+1 null child positions and 2n+1 total tokens.

Separate parse allocation from successful output

The parser builds O(n) nodes before return. A thrown parse may leave only unreachable local allocations; it does not modify a source tree or return a partial result.

Complexity

Let B be input/output character length. serialize is O(B) time, O(h) traversal wrappers excluding O(B) builder/result storage. deserialize takes O(B) time, O(B) token-array/string storage plus O(h) slot frames, and O(n) newly allocated output nodes. Fixed-width int tokens make B=O(n) on valid trees.

The recursive Baseline has the same grammar work but O(h) call frames and cannot handle arbitrary skew depth. Malformed text processing is O(B) until rejection; do not claim the iterative decoder uses only O(h) total auxiliary space while it retains split tokens.

Exact-state walkthroughs

Reveal normal and boundary traces

Round trip with explicit missing child slots

Input: {"tree":[1,2,3,null,4]} · Round-trip observations / parse outcome: {"serialized":"1,2,#,4,#,#,3,#,#","decoded":[1,2,3,null,4]}

Step 1 of 21: Serialize nullable items using nonnull wrapper entries.

Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.

Tree codec — preorder tokens and pending child slots

Phase: write-start. Current identity: null.

Original objects — unchanged source edges

T0: 1left → T1right → T2
T1: 2left → nullright → T3
T2: 3left → nullright → null
T3: 4left → nullright → null

Serialization wrappers — stack top at right; null means a nullable field

Preorder tokens emitted so far

Empty.

Fresh decoded D identities — partially filled edges

Empty tree.

Pending decoder slots — stack top at right

Empty.

A null decoded edge can still be unfilled while its slot is pending. Empty slots at successful end certify completion; leftover slots reject truncated data. Round-trip observations combine two calls for teaching; Java returns text and a fresh root separately.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]`
root	`"T0"`
serialStack	`["T0"]`
written	`[]`
text	`null`
decoded	`[]`
slots	`[]`
consumed	`0`
phase	`"write-start"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Item(Node node) {}
 9     private static final class Slot {
10         final Node node;
11         int next;
12         Slot(Node node) { this.node = node; }
13     }
14     private static Node token(String text) {
15         if (text.equals("#")) return null;
16         try {
17             int value = Integer.parseInt(text);
18             if (!Integer.toString(value).equals(text)) throw new IllegalArgumentException("noncanonical integer");
19             return new Node(value);
20         } catch (NumberFormatException exception) { throw new IllegalArgumentException("invalid token",exception); }
21     }
22     public static String serialize(Node root) {
23         StringBuilder text = new StringBuilder();
24         ArrayDeque<Item> stack = new ArrayDeque<>();
25         stack.push(new Item(root));
26         while (!stack.isEmpty()) {
27             Node node = stack.pop().node;
28             if (text.length() > 0) text.append(',');
29             if (node == null) text.append('#');
30             else {
31                 text.append(node.value);
32                 stack.push(new Item(node.right)); stack.push(new Item(node.left));
33             }
34         }
35         return text.toString();
36     }
37     public static Node deserialize(String text) {
38         Objects.requireNonNull(text,"text");
39         String[] tokens = text.split(",",-1);
40         Node root = token(tokens[0]);
41         if (root == null) {
42             if (tokens.length != 1) throw new IllegalArgumentException("trailing tokens");
43             return null;
44         }
45         int count = 1;
46         ArrayDeque<Slot> stack = new ArrayDeque<>(); stack.push(new Slot(root));
47         for (int i = 1; i < tokens.length; i++) {
48             if (stack.isEmpty()) throw new IllegalArgumentException("trailing tokens");
49             Slot parent = stack.peek();
50             Node child = token(tokens[i]);
51             if (child != null && ++count > 100000) throw new IllegalArgumentException("too many nodes");
52             if (parent.next == 0) { parent.node.left = child; parent.next = 1; }
53             else { parent.node.right = child; stack.pop(); }
54             if (child != null) stack.push(new Slot(child));
55         }
56         if (!stack.isEmpty()) throw new IllegalArgumentException("missing child token");
57         return root;
58     }
59     public static final class Baseline {
60         private static void write(Node node, StringBuilder text) {
61             if (text.length() > 0) text.append(',');
62             if (node == null) text.append('#');
63             else { text.append(node.value); write(node.left,text); write(node.right,text); }
64         }
65         public static String serialize(Node root) { StringBuilder text = new StringBuilder(); write(root,text); return text.toString(); }
66         private static Node read(String[] tokens, int[] cursor) {
67             if (cursor[0] == tokens.length) throw new IllegalArgumentException("missing token");
68             Node node = token(tokens[cursor[0]++]);
69             if (node != null) {
70                 if (++cursor[1] > 100000) throw new IllegalArgumentException("too many nodes");
71                 node.left = read(tokens,cursor); node.right = read(tokens,cursor);
72             }
73             return node;
74         }
75         public static Node deserialize(String text) {
76             Objects.requireNonNull(text,"text"); String[] tokens = text.split(",",-1); int[] cursor = {0,0};
77             Node root = read(tokens,cursor);
78             if (cursor[0] != tokens.length) throw new IllegalArgumentException("trailing tokens");
79             return root;
80         }
81     }
82 }
83

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Serialize nullable items using nonnull wrapper entries.
Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T0"]
written
[]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write-start"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2","T1"]
written
["1"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T0"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2","T3",null]
written
["1","2"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T1"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2","T3"]
written
["1","2","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2",null,null]
written
["1","2","#","4"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T3"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2",null]
written
["1","2","#","4","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
["T2"]
written
["1","2","#","4","#","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[null,null]
written
["1","2","#","4","#","#","3"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T2"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[null]
written
["1","2","#","4","#","#","3","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Parse a canonical root token into a fresh identity.
Decoded D identities are fresh and distinct from original T identities. A # root permits no extra tokens.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":null,"right":null}]
slots
[{"id":"D0","next":0}]
consumed
1
phase
"read-root"
current
"D0"
tokens
["1","2","#","4","#","#","3","#","#"]
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":null},{"id":"D1","value":2,"left":null,"right":null}]
slots
[{"id":"D0","next":1},{"id":"D1","next":0}]
consumed
2
phase
"read-child"
current
"D1"
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D0","side":"left","child":"D1"}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":null},{"id":"D1","value":2,"left":null,"right":null}]
slots
[{"id":"D0","next":1},{"id":"D1","next":1}]
consumed
3
phase
"read-child"
current
null
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D1","side":"left","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":null},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null}]
slots
[{"id":"D0","next":1},{"id":"D2","next":0}]
consumed
4
phase
"read-child"
current
"D2"
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D1","side":"right","child":"D2"}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":null},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null}]
slots
[{"id":"D0","next":1},{"id":"D2","next":1}]
consumed
5
phase
"read-child"
current
null
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D2","side":"left","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":null},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null}]
slots
[{"id":"D0","next":1}]
consumed
6
phase
"read-child"
current
null
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D2","side":"right","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":"D3"},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null},{"id":"D3","value":3,"left":null,"right":null}]
slots
[{"id":"D3","next":0}]
consumed
7
phase
"read-child"
current
"D3"
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D0","side":"right","child":"D3"}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":"D3"},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null},{"id":"D3","value":3,"left":null,"right":null}]
slots
[{"id":"D3","next":1}]
consumed
8
phase
"read-child"
current
null
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D3","side":"left","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":"D3"},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null},{"id":"D3","value":3,"left":null,"right":null}]
slots
[]
consumed
9
phase
"read-child"
current
null
tokens
["1","2","#","4","#","#","3","#","#"]
attachment
{"parent":"D3","side":"right","child":null}
Observe canonical text and the fresh decoded shape.
This walkthrough summarizes two API calls: serialization text and a level-order view of the freshly decoded tree. Java does not return a combined object.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["1","2","#","4","#","#","3","#","#"]
text
"1,2,#,4,#,#,3,#,#"
decoded
[{"id":"D0","value":1,"left":"D1","right":"D3"},{"id":"D1","value":2,"left":null,"right":"D2"},{"id":"D2","value":4,"left":null,"right":null},{"id":"D3","value":3,"left":null,"right":null}]
slots
[]
consumed
9
phase
"round-trip"
current
"D0"
tokens
["1","2","#","4","#","#","3","#","#"]
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
{"serialized":"1,2,#,4,#,#,3,#,#","decoded":[1,2,3,null,4]}

Empty tree is one null token

Input: {"tree":[]} · Round-trip observations / parse outcome: {"serialized":"#","decoded":[]}

Step 1 of 5: Serialize nullable items using nonnull wrapper entries.

Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.

Tree codec — preorder tokens and pending child slots

Phase: write-start. Current identity: null.

Original objects — unchanged source edges

Empty tree.

Serialization wrappers — stack top at right; null means a nullable field

null

Preorder tokens emitted so far

Empty.

Fresh decoded D identities — partially filled edges

Empty tree.

Pending decoder slots — stack top at right

Empty.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
serialStack	`[null]`
written	`[]`
text	`null`
decoded	`[]`
slots	`[]`
consumed	`0`
phase	`"write-start"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Item(Node node) {}
 9     private static final class Slot {
10         final Node node;
11         int next;
12         Slot(Node node) { this.node = node; }
13     }
14     private static Node token(String text) {
15         if (text.equals("#")) return null;
16         try {
17             int value = Integer.parseInt(text);
18             if (!Integer.toString(value).equals(text)) throw new IllegalArgumentException("noncanonical integer");
19             return new Node(value);
20         } catch (NumberFormatException exception) { throw new IllegalArgumentException("invalid token",exception); }
21     }
22     public static String serialize(Node root) {
23         StringBuilder text = new StringBuilder();
24         ArrayDeque<Item> stack = new ArrayDeque<>();
25         stack.push(new Item(root));
26         while (!stack.isEmpty()) {
27             Node node = stack.pop().node;
28             if (text.length() > 0) text.append(',');
29             if (node == null) text.append('#');
30             else {
31                 text.append(node.value);
32                 stack.push(new Item(node.right)); stack.push(new Item(node.left));
33             }
34         }
35         return text.toString();
36     }
37     public static Node deserialize(String text) {
38         Objects.requireNonNull(text,"text");
39         String[] tokens = text.split(",",-1);
40         Node root = token(tokens[0]);
41         if (root == null) {
42             if (tokens.length != 1) throw new IllegalArgumentException("trailing tokens");
43             return null;
44         }
45         int count = 1;
46         ArrayDeque<Slot> stack = new ArrayDeque<>(); stack.push(new Slot(root));
47         for (int i = 1; i < tokens.length; i++) {
48             if (stack.isEmpty()) throw new IllegalArgumentException("trailing tokens");
49             Slot parent = stack.peek();
50             Node child = token(tokens[i]);
51             if (child != null && ++count > 100000) throw new IllegalArgumentException("too many nodes");
52             if (parent.next == 0) { parent.node.left = child; parent.next = 1; }
53             else { parent.node.right = child; stack.pop(); }
54             if (child != null) stack.push(new Slot(child));
55         }
56         if (!stack.isEmpty()) throw new IllegalArgumentException("missing child token");
57         return root;
58     }
59     public static final class Baseline {
60         private static void write(Node node, StringBuilder text) {
61             if (text.length() > 0) text.append(',');
62             if (node == null) text.append('#');
63             else { text.append(node.value); write(node.left,text); write(node.right,text); }
64         }
65         public static String serialize(Node root) { StringBuilder text = new StringBuilder(); write(root,text); return text.toString(); }
66         private static Node read(String[] tokens, int[] cursor) {
67             if (cursor[0] == tokens.length) throw new IllegalArgumentException("missing token");
68             Node node = token(tokens[cursor[0]++]);
69             if (node != null) {
70                 if (++cursor[1] > 100000) throw new IllegalArgumentException("too many nodes");
71                 node.left = read(tokens,cursor); node.right = read(tokens,cursor);
72             }
73             return node;
74         }
75         public static Node deserialize(String text) {
76             Objects.requireNonNull(text,"text"); String[] tokens = text.split(",",-1); int[] cursor = {0,0};
77             Node root = read(tokens,cursor);
78             if (cursor[0] != tokens.length) throw new IllegalArgumentException("trailing tokens");
79             return root;
80         }
81     }
82 }
83

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Serialize nullable items using nonnull wrapper entries.
Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.
treeNodes
[]
root
null
serialStack
[null]
written
[]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write-start"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[]
root
null
serialStack
[]
written
["#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Parse a canonical root token into a fresh identity.
Decoded D identities are fresh and distinct from original T identities. A # root permits no extra tokens.
treeNodes
[]
root
null
serialStack
[]
written
["#"]
text
"#"
decoded
[]
slots
[]
consumed
1
phase
"read-root"
current
null
tokens
["#"]
Observe canonical text and the fresh decoded shape.
This walkthrough summarizes two API calls: serialization text and a level-order view of the freshly decoded tree. Java does not return a combined object.
treeNodes
[]
root
null
serialStack
[]
written
["#"]
text
"#"
decoded
[]
slots
[]
consumed
1
phase
"round-trip"
current
null
tokens
["#"]
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
{"serialized":"#","decoded":[]}

Truncated text leaves a pending right slot

Input: {"text":"1,#"} · Round-trip observations / parse outcome: {"error":"IllegalArgumentException"}

Step 1 of 4: Parse a canonical root token into a fresh identity.

Decoded D identities are fresh and distinct from original T identities. A # root permits no extra tokens.

Tree codec — preorder tokens and pending child slots

Phase: read-root. Current identity: D0.

Original objects — unchanged source edges

Empty tree.

Serialization wrappers — stack top at right; null means a nullable field

Empty.

Preorder tokens emitted so far

Empty.

Text: 1,#. Tokens consumed: 1.

Fresh decoded D identities — partially filled edges

D0: 1left → nullright → null

Pending decoder slots — stack top at right

D0: next left child

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
serialStack	`[]`
written	`[]`
text	`"1,#"`
decoded	`[{"id":"D0","value":1,"left":null,"right":null}]`
slots	`[{"id":"D0","next":0}]`
consumed	`1`
phase	`"read-root"`
current	`"D0"`
tokens	`["1","#"]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Item(Node node) {}
 9     private static final class Slot {
10         final Node node;
11         int next;
12         Slot(Node node) { this.node = node; }
13     }
14     private static Node token(String text) {
15         if (text.equals("#")) return null;
16         try {
17             int value = Integer.parseInt(text);
18             if (!Integer.toString(value).equals(text)) throw new IllegalArgumentException("noncanonical integer");
19             return new Node(value);
20         } catch (NumberFormatException exception) { throw new IllegalArgumentException("invalid token",exception); }
21     }
22     public static String serialize(Node root) {
23         StringBuilder text = new StringBuilder();
24         ArrayDeque<Item> stack = new ArrayDeque<>();
25         stack.push(new Item(root));
26         while (!stack.isEmpty()) {
27             Node node = stack.pop().node;
28             if (text.length() > 0) text.append(',');
29             if (node == null) text.append('#');
30             else {
31                 text.append(node.value);
32                 stack.push(new Item(node.right)); stack.push(new Item(node.left));
33             }
34         }
35         return text.toString();
36     }
37     public static Node deserialize(String text) {
38         Objects.requireNonNull(text,"text");
39         String[] tokens = text.split(",",-1);
40         Node root = token(tokens[0]);
41         if (root == null) {
42             if (tokens.length != 1) throw new IllegalArgumentException("trailing tokens");
43             return null;
44         }
45         int count = 1;
46         ArrayDeque<Slot> stack = new ArrayDeque<>(); stack.push(new Slot(root));
47         for (int i = 1; i < tokens.length; i++) {
48             if (stack.isEmpty()) throw new IllegalArgumentException("trailing tokens");
49             Slot parent = stack.peek();
50             Node child = token(tokens[i]);
51             if (child != null && ++count > 100000) throw new IllegalArgumentException("too many nodes");
52             if (parent.next == 0) { parent.node.left = child; parent.next = 1; }
53             else { parent.node.right = child; stack.pop(); }
54             if (child != null) stack.push(new Slot(child));
55         }
56         if (!stack.isEmpty()) throw new IllegalArgumentException("missing child token");
57         return root;
58     }
59     public static final class Baseline {
60         private static void write(Node node, StringBuilder text) {
61             if (text.length() > 0) text.append(',');
62             if (node == null) text.append('#');
63             else { text.append(node.value); write(node.left,text); write(node.right,text); }
64         }
65         public static String serialize(Node root) { StringBuilder text = new StringBuilder(); write(root,text); return text.toString(); }
66         private static Node read(String[] tokens, int[] cursor) {
67             if (cursor[0] == tokens.length) throw new IllegalArgumentException("missing token");
68             Node node = token(tokens[cursor[0]++]);
69             if (node != null) {
70                 if (++cursor[1] > 100000) throw new IllegalArgumentException("too many nodes");
71                 node.left = read(tokens,cursor); node.right = read(tokens,cursor);
72             }
73             return node;
74         }
75         public static Node deserialize(String text) {
76             Objects.requireNonNull(text,"text"); String[] tokens = text.split(",",-1); int[] cursor = {0,0};
77             Node root = read(tokens,cursor);
78             if (cursor[0] != tokens.length) throw new IllegalArgumentException("trailing tokens");
79             return root;
80         }
81     }
82 }
83

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Parse a canonical root token into a fresh identity.
Decoded D identities are fresh and distinct from original T identities. A # root permits no extra tokens.
treeNodes
[]
root
null
serialStack
[]
written
[]
text
"1,#"
decoded
[{"id":"D0","value":1,"left":null,"right":null}]
slots
[{"id":"D0","next":0}]
consumed
1
phase
"read-root"
current
"D0"
tokens
["1","#"]
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[]
root
null
serialStack
[]
written
[]
text
"1,#"
decoded
[{"id":"D0","value":1,"left":null,"right":null}]
slots
[{"id":"D0","next":1}]
consumed
2
phase
"read-child"
current
null
tokens
["1","#"]
attachment
{"parent":"D0","side":"left","child":null}
Reject an unfinished grammar continuation.
End of text arrived while a node still needs a child token. No partial tree is returned.
treeNodes
[]
root
null
serialStack
[]
written
[]
text
"1,#"
decoded
[{"id":"D0","value":1,"left":null,"right":null}]
slots
[{"id":"D0","next":1}]
consumed
2
phase
"reject"
current
null
tokens
["1","#"]
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
{"error":"IllegalArgumentException"}

Full int values remain canonical

Input: {"tree":[-2147483648,null,2147483647]} · Round-trip observations / parse outcome: {"serialized":"-2147483648,#,2147483647,#,#","decoded":[-2147483648,null,2147483647]}

Step 1 of 13: Serialize nullable items using nonnull wrapper entries.

Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.

Tree codec — preorder tokens and pending child slots

Phase: write-start. Current identity: null.

Original objects — unchanged source edges

T0: -2147483648left → nullright → T1
T1: 2147483647left → nullright → null

Serialization wrappers — stack top at right; null means a nullable field

Preorder tokens emitted so far

Empty.

Fresh decoded D identities — partially filled edges

Empty tree.

Pending decoder slots — stack top at right

Empty.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]`
root	`"T0"`
serialStack	`["T0"]`
written	`[]`
text	`null`
decoded	`[]`
slots	`[]`
consumed	`0`
phase	`"write-start"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Item(Node node) {}
 9     private static final class Slot {
10         final Node node;
11         int next;
12         Slot(Node node) { this.node = node; }
13     }
14     private static Node token(String text) {
15         if (text.equals("#")) return null;
16         try {
17             int value = Integer.parseInt(text);
18             if (!Integer.toString(value).equals(text)) throw new IllegalArgumentException("noncanonical integer");
19             return new Node(value);
20         } catch (NumberFormatException exception) { throw new IllegalArgumentException("invalid token",exception); }
21     }
22     public static String serialize(Node root) {
23         StringBuilder text = new StringBuilder();
24         ArrayDeque<Item> stack = new ArrayDeque<>();
25         stack.push(new Item(root));
26         while (!stack.isEmpty()) {
27             Node node = stack.pop().node;
28             if (text.length() > 0) text.append(',');
29             if (node == null) text.append('#');
30             else {
31                 text.append(node.value);
32                 stack.push(new Item(node.right)); stack.push(new Item(node.left));
33             }
34         }
35         return text.toString();
36     }
37     public static Node deserialize(String text) {
38         Objects.requireNonNull(text,"text");
39         String[] tokens = text.split(",",-1);
40         Node root = token(tokens[0]);
41         if (root == null) {
42             if (tokens.length != 1) throw new IllegalArgumentException("trailing tokens");
43             return null;
44         }
45         int count = 1;
46         ArrayDeque<Slot> stack = new ArrayDeque<>(); stack.push(new Slot(root));
47         for (int i = 1; i < tokens.length; i++) {
48             if (stack.isEmpty()) throw new IllegalArgumentException("trailing tokens");
49             Slot parent = stack.peek();
50             Node child = token(tokens[i]);
51             if (child != null && ++count > 100000) throw new IllegalArgumentException("too many nodes");
52             if (parent.next == 0) { parent.node.left = child; parent.next = 1; }
53             else { parent.node.right = child; stack.pop(); }
54             if (child != null) stack.push(new Slot(child));
55         }
56         if (!stack.isEmpty()) throw new IllegalArgumentException("missing child token");
57         return root;
58     }
59     public static final class Baseline {
60         private static void write(Node node, StringBuilder text) {
61             if (text.length() > 0) text.append(',');
62             if (node == null) text.append('#');
63             else { text.append(node.value); write(node.left,text); write(node.right,text); }
64         }
65         public static String serialize(Node root) { StringBuilder text = new StringBuilder(); write(root,text); return text.toString(); }
66         private static Node read(String[] tokens, int[] cursor) {
67             if (cursor[0] == tokens.length) throw new IllegalArgumentException("missing token");
68             Node node = token(tokens[cursor[0]++]);
69             if (node != null) {
70                 if (++cursor[1] > 100000) throw new IllegalArgumentException("too many nodes");
71                 node.left = read(tokens,cursor); node.right = read(tokens,cursor);
72             }
73             return node;
74         }
75         public static Node deserialize(String text) {
76             Objects.requireNonNull(text,"text"); String[] tokens = text.split(",",-1); int[] cursor = {0,0};
77             Node root = read(tokens,cursor);
78             if (cursor[0] != tokens.length) throw new IllegalArgumentException("trailing tokens");
79             return root;
80         }
81     }
82 }
83

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Serialize nullable items using nonnull wrapper entries.
Serialization work has top at the right. A null identity means an Item whose node field is null, not a null deque element.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
["T0"]
written
[]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write-start"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
["T1",null]
written
["-2147483648"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T0"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
["T1"]
written
["-2147483648","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[null,null]
written
["-2147483648","#","2147483647"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
"T1"
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[null]
written
["-2147483648","#","2147483647","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Write one preorder value or explicit null token.
A value schedules right then left; each missing child contributes #. Values without these null positions do not determine shape.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
null
decoded
[]
slots
[]
consumed
0
phase
"write"
current
null
Parse a canonical root token into a fresh identity.
Decoded D identities are fresh and distinct from original T identities. A # root permits no extra tokens.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":null}]
slots
[{"id":"D0","next":0}]
consumed
1
phase
"read-root"
current
"D0"
tokens
["-2147483648","#","2147483647","#","#"]
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":null}]
slots
[{"id":"D0","next":1}]
consumed
2
phase
"read-child"
current
null
tokens
["-2147483648","#","2147483647","#","#"]
attachment
{"parent":"D0","side":"left","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":"D1"},{"id":"D1","value":2147483647,"left":null,"right":null}]
slots
[{"id":"D1","next":0}]
consumed
3
phase
"read-child"
current
"D1"
tokens
["-2147483648","#","2147483647","#","#"]
attachment
{"parent":"D0","side":"right","child":"D1"}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":"D1"},{"id":"D1","value":2147483647,"left":null,"right":null}]
slots
[{"id":"D1","next":1}]
consumed
4
phase
"read-child"
current
null
tokens
["-2147483648","#","2147483647","#","#"]
attachment
{"parent":"D1","side":"left","child":null}
Fill the next preorder child slot and schedule any child slots.
A right assignment completes the parent frame, but a newly allocated child still owns its own pending left/right slots.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":"D1"},{"id":"D1","value":2147483647,"left":null,"right":null}]
slots
[]
consumed
5
phase
"read-child"
current
null
tokens
["-2147483648","#","2147483647","#","#"]
attachment
{"parent":"D1","side":"right","child":null}
Observe canonical text and the fresh decoded shape.
This walkthrough summarizes two API calls: serialization text and a level-order view of the freshly decoded tree. Java does not return a combined object.
treeNodes
[{"id":"T0","value":-2147483648,"left":null,"right":"T1"},{"id":"T1","value":2147483647,"left":null,"right":null}]
root
"T0"
serialStack
[]
written
["-2147483648","#","2147483647","#","#"]
text
"-2147483648,#,2147483647,#,#"
decoded
[{"id":"D0","value":-2147483648,"left":null,"right":"D1"},{"id":"D1","value":2147483647,"left":null,"right":null}]
slots
[]
consumed
5
phase
"round-trip"
current
"D0"
tokens
["-2147483648","#","2147483647","#","#"]
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
{"serialized":"-2147483648,#,2147483647,#,#","decoded":[-2147483648,null,2147483647]}

Test the contract

Input: null tree
Output: text #; decoded null
One null grammar token.
Input: Duplicate-valued asymmetric tree
Output: shape and values preserved in a fresh graph
Values alone are insufficient.
Input: Missing/trailing/empty/noncanonical token
Output: IllegalArgumentException
Strict full-message parsing.
Input: 100,000-node chain
Output: successful iterative round trip
Deep valid data.
Input: 100,001 nonnull tokens forming a tree
Output: IllegalArgumentException
Decoded node limit enforced.

Common mistakes and counterexamples

Omit null markers

Counterexample: [1,2] and [1,null,2] have the same value preorder.

Encode every absent child as #.

Accept a valid prefix and ignore the suffix

Counterexample: 1,#,#,# contains an extra tree token.

Require complete slot closure and no trailing tokens.

Use parseInt as the canonical grammar check

Counterexample: +1, 01 or Unicode digits may parse but are not the chosen format.

Round-trip each integer token through Integer.toString and compare exactly.

Use recursive parsing at the full depth bound

Counterexample: A valid 100,000-node chain can overflow the call stack.

Store pending child continuations explicitly.

Follow-ups

Stream tokens instead of split.

A cursor/tokenizer can remove O(B) token-array retention. It must still validate canonical tokens, exact grammar completion, size bounds, and end-of-stream errors.

Use a compact binary format.

Define int byte order, presence bits, versioning and truncation behavior. A smaller representation does not remove shape or validation requirements.

Serialize graphs with sharing or cycles.

Introduce explicit object IDs and back-references with a defined reference-validation policy. This tree grammar duplicates sharing and cannot represent cycles.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 238/20,000 characters

Self-review

Can I state why null markers make preorder unambiguous?Can I distinguish successful return from unreachable partial allocations on failure?Can I account for token-array memory and prove fresh node ownership?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.