Tree Construction & Serialization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Challenges we must handle during deserialization:
 
# 1. EMPTY INPUT
input_1 = ""
# Expected: return None (empty tree)
 
# 2. SINGLE NODE
input_2 = "42"
# Expected: TreeNode(42) with no children
 
# 3. MALFORMED - missing values
input_3 = "1,2,,3"
# Question: Is "" a value, null, or error?
 
# 4. MALFORMED - unbalanced structure  
input_4 = "1,2,3,4"  # Preorder format expecting nulls
# This might be valid or invalid depending on interpretation
 
# 5. MALFORMED - wrong number of nulls
input_5 = "1,null,null,null"
# Too many nulls - third null is orphaned
 
# 6. WRONG DATA TYPE
input_6 = "1,abc,3"
# "abc" cannot be parsed as integer
 
# 7. VERY DEEP (stack overflow risk)
input_7 = "1," + ",".join(["2,null" for _ in range(10000)])
# Deep left-skewed tree
 
# 8. VERY WIDE (memory pressure)
input_8 = ",".join([str(i) for i in range(1000000)])
# If level-order, could be valid and huge
 
# Robust deserialization must handle ALL these cases!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

from typing import Optional, List, Iterator
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
    
    def __repr__(self):
        return f"TreeNode({self.val})"
 
class PreorderDeserializer:
    """
    Robust recursive descent deserializer for preorder-with-nulls format.
    
    Features:
    - Input validation
    - Meaningful error messages
    - Handles edge cases
    """
    
    NULL_MARKER = "null"
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """
        Main entry point for deserialization.
        
        Args:
            data: Serialized tree string (e.g., "1,2,null,null,3,null,null")
            
        Returns:
            Root of reconstructed tree, or None for empty tree
            
        Raises:
            ValueError: If input is malformed
        """
        # Handle empty input
        if not data or data.strip() == "":
            return None
        
        # Tokenize
        tokens = self._tokenize(data)
        if not tokens:
            return None
        
        # Check for single null (empty tree)
        if len(tokens) == 1 and tokens[0] == self.NULL_MARKER:
            return None
        
        # Create iterator for token consumption
        token_iter = iter(tokens)
        
        # Build tree
        root = self._build_tree(token_iter)
        
        # Verify all tokens consumed (catch malformed input)
        remaining = list(token_iter)
        if remaining:
            raise ValueError(
                f"Malformed input: {len(remaining)} unconsumed tokens: {remaining[:5]}..."
            )
        
        return root
    
    def _tokenize(self, data: str) -> List[str]:
        """
        Split input string into tokens.
        
        Handles:
        - Comma-separated values
        - Whitespace trimming
        - Empty token detection
        """
        tokens = []
        for i, token in enumerate(data.split(",")):
            token = token.strip()
            if token == "":
                raise ValueError(f"Empty token at position {i}")
            tokens.append(token)
        return tokens
    
    def _build_tree(self, tokens: Iterator[str]) -> Optional[TreeNode]:
        """
        Recursive descent parser that consumes tokens as it builds.
        
        Each call consumes exactly the tokens for one subtree.
        """
        try:
            token = next(tokens)
        except StopIteration:
            raise ValueError("Unexpected end of input: expected value or null")
        
        # Null marker terminates this branch
        if token == self.NULL_MARKER:
            return None
        
        # Parse value
        try:
            val = int(token)
        except ValueError:
            raise ValueError(f"Cannot parse '{token}' as integer")
        
        # Create node
        node = TreeNode(val)
        
        # Recursively build children
        # Left child consumes its tokens, then right child consumes its tokens
        node.left = self._build_tree(tokens)
        node.right = self._build_tree(tokens)
        
        return node
 
# Test the deserializer
deserializer = PreorderDeserializer()
 
# Normal case
tree = deserializer.deserialize("1,2,null,null,3,4,null,null,5,null,null")
print(f"Root: {tree}")           # TreeNode(1)
print(f"Left: {tree.left}")      # TreeNode(2)
print(f"Right: {tree.right}")    # TreeNode(3)
 
# Edge cases
empty_tree = deserializer.deserialize("")
print(f"Empty: {empty_tree}")    # None
 
single_node = deserializer.deserialize("42")
# Wait - this should fail! A single node needs null markers for children
# Let's see what happens...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class LenientPreorderDeserializer:
    """
    More lenient deserializer that handles incomplete input gracefully.
    
    Missing trailing nulls are implied (common in optimized serializations).
    """
    
    NULL_MARKER = "null"
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data or data.strip() == "":
            return None
        
        tokens = [t.strip() for t in data.split(",")]
        if tokens == [self.NULL_MARKER]:
            return None
        
        self.index = 0
        self.tokens = tokens
        return self._build_tree()
    
    def _build_tree(self) -> Optional[TreeNode]:
        # If we've exhausted tokens, treat as null (lenient behavior)
        if self.index >= len(self.tokens):
            return None
        
        token = self.tokens[self.index]
        self.index += 1
        
        if token == self.NULL_MARKER:
            return None
        
        node = TreeNode(int(token))
        node.left = self._build_tree()
        node.right = self._build_tree()
        return node
 
# Now single node works
deserializer = LenientPreorderDeserializer()
single = deserializer.deserialize("42")
print(f"Value: {single.val}")     # 42
print(f"Left: {single.left}")     # None
print(f"Right: {single.right}")   # None
 
# Incomplete but valid
partial = deserializer.deserialize("1,2")
# Interpreted as:
#     1
#    / \
#   2   None
# With 2's children also None
print(f"1's left: {partial.left.val}")  # 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

from collections import deque
from typing import Optional, List
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
 
class LevelOrderDeserializer:
    """
    Queue-based deserializer for level-order serialized trees.
    
    Input format: "1,2,3,null,null,4,5" (LeetCode-style)
    
    Key insight: The queue holds nodes waiting for their children.
    Each iteration assigns children to one parent.
    """
    
    NULL_MARKER = "null"
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """
        Reconstruct tree from level-order string.
        
        Time: O(n)
        Space: O(w) where w is max width of tree
        """
        if not data or data.strip() == "":
            return None
        
        tokens = [t.strip() for t in data.split(",")]
        
        if not tokens or tokens[0] == self.NULL_MARKER:
            return None
        
        # Create root
        root = TreeNode(self._parse_value(tokens[0]))
        
        # Queue of nodes waiting for children
        queue: deque = deque([root])
        index = 1
        
        while queue and index < len(tokens):
            # Get next parent
            parent = queue.popleft()
            
            # Assign left child
            if index < len(tokens):
                left_val = tokens[index]
                index += 1
                
                if left_val != self.NULL_MARKER:
                    parent.left = TreeNode(self._parse_value(left_val))
                    queue.append(parent.left)
            
            # Assign right child
            if index < len(tokens):
                right_val = tokens[index]
                index += 1
                
                if right_val != self.NULL_MARKER:
                    parent.right = TreeNode(self._parse_value(right_val))
                    queue.append(parent.right)
        
        return root
    
    def _parse_value(self, token: str) -> int:
        """Parse token as integer with error handling."""
        try:
            return int(token)
        except ValueError:
            raise ValueError(f"Cannot parse '{token}' as integer")
 
# Test
deserializer = LevelOrderDeserializer()
 
# LeetCode-style input
tree = deserializer.deserialize("1,2,3,null,null,4,5")
# Resulting tree:
#       1
#      / \
#     2   3
#        / \
#       4   5
 
print(f"Root: {tree.val}")                    # 1
print(f"Root.left: {tree.left.val}")          # 2
print(f"Root.right: {tree.right.val}")        # 3
print(f"Root.right.left: {tree.right.left.val}")   # 4
print(f"Root.right.right: {tree.right.right.val}") # 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# Input: "1,2,3,null,null,4,5"
# Tokens: [1, 2, 3, null, null, 4, 5]
 
# Step 0: Create root
# Root = Node(1)
# Queue = [Node(1)]
# Index = 1
 
# Step 1: Process Node(1)
# Dequeue Node(1)
# tokens[1] = "2" -> Node(1).left = Node(2), enqueue Node(2)
# tokens[2] = "3" -> Node(1).right = Node(3), enqueue Node(3)
# Queue = [Node(2), Node(3)]
# Index = 3
 
# Step 2: Process Node(2)
# Dequeue Node(2)
# tokens[3] = "null" -> Node(2).left = None
# tokens[4] = "null" -> Node(2).right = None
# Queue = [Node(3)]
# Index = 5
 
# Step 3: Process Node(3)
# Dequeue Node(3)
# tokens[5] = "4" -> Node(3).left = Node(4), enqueue Node(4)
# tokens[6] = "5" -> Node(3).right = Node(5), enqueue Node(5)
# Queue = [Node(4), Node(5)]
# Index = 7
 
# Step 4: Index >= len(tokens), we're done!
# (Remaining queue nodes are leaves - they have no children to assign)
 
# Result:
#       1
#      / \
#     2   3
#        / \
#       4   5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

from typing import Optional, Generator, Iterator, IO
import io
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
 
class StreamingDeserializer:
    """
    Deserializes trees from a stream (file, network socket, etc.)
    without loading the entire input into memory.
    
    Useful for:
    - Very large trees that don't fit in memory as a string
    - Network streams where data arrives incrementally
    - Processing trees from disk without full file load
    """
    
    NULL_MARKER = "null"
    DELIMITER = ","
    
    def deserialize_from_stream(self, stream: IO[str]) -> Optional[TreeNode]:
        """
        Build tree from a character stream.
        
        Args:
            stream: Any file-like object with a read() method
            
        Returns:
            Root of reconstructed tree
        """
        token_gen = self._token_generator(stream)
        return self._build_tree(token_gen)
    
    def _token_generator(self, stream: IO[str]) -> Generator[str, None, None]:
        """
        Reads stream character by character, yielding complete tokens.
        
        Memory usage: O(max_token_length), not O(input_size)
        """
        buffer = []
        
        while True:
            char = stream.read(1)
            
            if not char:  # End of stream
                if buffer:
                    yield "".join(buffer)
                return
            
            if char == self.DELIMITER:
                if buffer:
                    yield "".join(buffer)
                    buffer = []
            elif char.isspace():
                continue  # Skip whitespace
            else:
                buffer.append(char)
    
    def _build_tree(self, tokens: Iterator[str]) -> Optional[TreeNode]:
        """Recursive tree builder (same as before)."""
        try:
            token = next(tokens)
        except StopIteration:
            return None
        
        if token == self.NULL_MARKER:
            return None
        
        node = TreeNode(int(token))
        node.left = self._build_tree(tokens)
        node.right = self._build_tree(tokens)
        return node
 
# Example: Deserialize from a file
def deserialize_from_file(filepath: str) -> Optional[TreeNode]:
    """Read tree from file without loading entire file."""
    deserializer = StreamingDeserializer()
    with open(filepath, 'r') as f:
        return deserializer.deserialize_from_stream(f)
 
# Example: Deserialize from a string IO (for testing)
def test_streaming():
    deserializer = StreamingDeserializer()
    
    # Simulate a stream using StringIO
    data = "1,2,null,null,3,null,null"
    stream = io.StringIO(data)
    
    tree = deserializer.deserialize_from_stream(stream)
    print(f"Root: {tree.val}")        # 1
    print(f"Left: {tree.left.val}")   # 2
    print(f"Right: {tree.right.val}") # 3
 
test_streaming()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class BufferedStreamingDeserializer:
    """
    Buffered streaming for better I/O performance.
    
    Reads in chunks (e.g., 8KB) while maintaining streaming semantics.
    """
    
    NULL_MARKER = "null"
    BUFFER_SIZE = 8192  # 8KB chunks
    
    def _token_generator(self, stream: IO[str]) -> Generator[str, None, None]:
        """
        Buffered token generation.
        
        Reads in chunks for efficiency while yielding one token at a time.
        """
        current_token = []
        
        while True:
            chunk = stream.read(self.BUFFER_SIZE)
            
            if not chunk:
                # End of stream
                if current_token:
                    yield "".join(current_token)
                return
            
            for char in chunk:
                if char == ',':
                    if current_token:
                        yield "".join(current_token)
                        current_token = []
                elif not char.isspace():
                    current_token.append(char)
 
# Memory usage comparison for a 1GB serialized tree:
#
# Non-streaming: 1GB string + 1GB tokens list + tree = ~2GB+ RAM
# Streaming (char by char): ~100 bytes buffer + tree = tree size RAM
# Buffered streaming: 8KB buffer + tree = tree size RAM + 8KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

from typing import Optional, List, Tuple
from dataclasses import dataclass
from enum import Enum
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
 
class ValidationErrorType(Enum):
    EMPTY_INPUT = "empty_input"
    EMPTY_TOKEN = "empty_token"
    PARSE_ERROR = "parse_error"
    STRUCTURAL_ERROR = "structural_error"
    DEPTH_EXCEEDED = "depth_exceeded"
    NODE_LIMIT_EXCEEDED = "node_limit_exceeded"
 
@dataclass
class ValidationError:
    error_type: ValidationErrorType
    message: str
    position: Optional[int] = None
    token: Optional[str] = None
 
@dataclass
class DeserializationResult:
    """Result object containing either a tree or errors."""
    tree: Optional[TreeNode]
    errors: List[ValidationError]
    node_count: int
    max_depth: int
    
    @property
    def success(self) -> bool:
        return len(self.errors) == 0 and self.tree is not None
 
class ValidatedDeserializer:
    """
    Production-grade deserializer with comprehensive validation.
    
    Features:
    - Configurable limits (max depth, max nodes)
    - Detailed error reporting
    - Statistics about deserialized tree
    - Safe defaults
    """
    
    NULL_MARKER = "null"
    DEFAULT_MAX_DEPTH = 1000
    DEFAULT_MAX_NODES = 1_000_000
    
    def __init__(
        self, 
        max_depth: int = DEFAULT_MAX_DEPTH,
        max_nodes: int = DEFAULT_MAX_NODES
    ):
        self.max_depth = max_depth
        self.max_nodes = max_nodes
    
    def deserialize(self, data: str) -> DeserializationResult:
        """
        Deserialize with full validation.
        
        Returns a result object with the tree (if successful),
        any errors encountered, and tree statistics.
        """
        errors: List[ValidationError] = []
        
        # Stage 1: Handle empty input
        if not data or data.strip() == "":
            return DeserializationResult(
                tree=None,
                errors=[],  # Empty input is valid - it's an empty tree
                node_count=0,
                max_depth=0
            )
        
        # Stage 2: Tokenize with validation
        tokens, tokenize_errors = self._tokenize_and_validate(data)
        if tokenize_errors:
            return DeserializationResult(
                tree=None,
                errors=tokenize_errors,
                node_count=0,
                max_depth=0
            )
        
        # Handle single null
        if tokens == [self.NULL_MARKER]:
            return DeserializationResult(
                tree=None,
                errors=[],
                node_count=0,
                max_depth=0
            )
        
        # Stage 3: Build tree with structural validation
        self.token_index = 0
        self.tokens = tokens
        self.node_count = 0
        self.current_max_depth = 0
        self.build_errors: List[ValidationError] = []
        
        try:
            tree = self._build_tree_validated(depth=0)
        except RecursionError:
            return DeserializationResult(
                tree=None,
                errors=[ValidationError(
                    ValidationErrorType.DEPTH_EXCEEDED,
                    "Recursion limit exceeded (tree too deep)"
                )],
                node_count=self.node_count,
                max_depth=self.current_max_depth
            )
        
        if self.build_errors:
            return DeserializationResult(
                tree=None,
                errors=self.build_errors,
                node_count=self.node_count,
                max_depth=self.current_max_depth
            )
        
        # Stage 4: Verify all tokens consumed
        if self.token_index < len(self.tokens):
            remaining = len(self.tokens) - self.token_index
            return DeserializationResult(
                tree=None,
                errors=[ValidationError(
                    ValidationErrorType.STRUCTURAL_ERROR,
                    f"Malformed input: {remaining} unconsumed tokens",
                    position=self.token_index
                )],
                node_count=self.node_count,
                max_depth=self.current_max_depth
            )
        
        return DeserializationResult(
            tree=tree,
            errors=[],
            node_count=self.node_count,
            max_depth=self.current_max_depth
        )
    
    def _tokenize_and_validate(
        self, 
        data: str
    ) -> Tuple[List[str], List[ValidationError]]:
        """Tokenize input and detect syntactic errors."""
        tokens = []
        errors = []
        
        for i, raw_token in enumerate(data.split(",")):
            token = raw_token.strip()
            
            if token == "":
                errors.append(ValidationError(
                    ValidationErrorType.EMPTY_TOKEN,
                    f"Empty token at position {i}",
                    position=i
                ))
                continue
            
            # Validate token format
            if token != self.NULL_MARKER:
                try:
                    int(token)  # Just validate, don't store
                except ValueError:
                    errors.append(ValidationError(
                        ValidationErrorType.PARSE_ERROR,
                        f"Cannot parse '{token}' as integer",
                        position=i,
                        token=token
                    ))
            
            tokens.append(token)
        
        return tokens, errors
    
    def _build_tree_validated(self, depth: int) -> Optional[TreeNode]:
        """Build tree with depth and node count validation."""
        # Check depth limit
        if depth > self.max_depth:
            self.build_errors.append(ValidationError(
                ValidationErrorType.DEPTH_EXCEEDED,
                f"Tree depth {depth} exceeds maximum {self.max_depth}"
            ))
            return None
        
        # Check if tokens exhausted
        if self.token_index >= len(self.tokens):
            return None
        
        token = self.tokens[self.token_index]
        self.token_index += 1
        
        if token == self.NULL_MARKER:
            return None
        
        # Check node limit
        self.node_count += 1
        if self.node_count > self.max_nodes:
            self.build_errors.append(ValidationError(
                ValidationErrorType.NODE_LIMIT_EXCEEDED,
                f"Node count exceeds maximum {self.max_nodes}"
            ))
            return None
        
        # Update max depth tracking
        self.current_max_depth = max(self.current_max_depth, depth)
        
        node = TreeNode(int(token))
        node.left = self._build_tree_validated(depth + 1)
        node.right = self._build_tree_validated(depth + 1)
        return node
 
# Usage example
deserializer = ValidatedDeserializer(max_depth=100, max_nodes=10000)
 
# Valid input
result = deserializer.deserialize("1,2,null,null,3,null,null")
if result.success:
    print(f"Success! {result.node_count} nodes, depth {result.max_depth}")
else:
    print(f"Failed: {result.errors}")
 
# Invalid input
result = deserializer.deserialize("1,abc,3")
print(f"Errors: {result.errors}")
# [ValidationError(PARSE_ERROR, "Cannot parse 'abc' as integer", ...)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

# SLOW: Split creates a whole new list
tokens = data.split(",")  # O(n) memory allocation
 
# FASTER: Find delimiters as you go
def iter_tokens(data: str):
    """Iterator that yields tokens without creating a list."""
    start = 0
    for i, char in enumerate(data):
        if char == ',':
            yield data[start:i]
            start = i + 1
    if start < len(data):
        yield data[start:]
 
# FASTEST: Use a scanning parser
class ScanningParser:
    """
    Parse without creating intermediate token strings.
    
    Instead of: string -> tokens -> tree
    We do: string -> tree directly
    """
    
    def __init__(self, data: str):
        self.data = data
        self.pos = 0
        self.length = len(data)
    
    def next_token(self) -> tuple:
        """
        Returns (is_null, value) without creating string objects.
        
        is_null: True if token is "null"
        value: Integer value if not null
        """
        # Skip whitespace
        while self.pos < self.length and self.data[self.pos].isspace():
            self.pos += 1
        
        if self.pos >= self.length:
            raise StopIteration
        
        start = self.pos
        
        # Find end of token
        while self.pos < self.length and self.data[self.pos] not in ', ':
            self.pos += 1
        
        token_slice = self.data[start:self.pos]
        
        # Skip delimiter
        if self.pos < self.length and self.data[self.pos] == ',':
            self.pos += 1
        
        if token_slice == "null":
            return (True, 0)
        else:
            return (False, int(token_slice))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class TreeNodePool:
    """
    Object pool for TreeNode instances.
    
    Reduces garbage collection overhead by reusing node objects.
    Useful when deserializing and then discarding many trees.
    """
    
    def __init__(self, initial_size: int = 1000):
        self.pool = [TreeNode(0) for _ in range(initial_size)]
        self.pool_index = 0
    
    def acquire(self, val: int) -> TreeNode:
        """Get a node from the pool or create a new one."""
        if self.pool_index < len(self.pool):
            node = self.pool[self.pool_index]
            node.val = val
            node.left = None
            node.right = None
            self.pool_index += 1
            return node
        else:
            # Pool exhausted, create new node
            return TreeNode(val)
    
    def release_all(self):
        """Return all nodes to pool (call when done with tree)."""
        self.pool_index = 0
 
# Using the pool
pool = TreeNodePool(10000)
 
# Deserialize many trees
for data in tree_data_list:
    root = deserialize_with_pool(data, pool)
    process_tree(root)
    pool.release_all()  # Nodes ready for reuse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class IterativeDeserializer:
    """
    Fully iterative deserialization using explicit stack.
    
    Benefits:
    - No stack overflow for deep trees
    - Slightly faster (no function call overhead)
    - Easier to add instrumentation/progress tracking
    """
    
    NULL_MARKER = "null"
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data or data == self.NULL_MARKER:
            return None
        
        tokens = data.split(",")
        
        root = TreeNode(int(tokens[0]))
        
        # Stack entries: (parent_node, is_left_child)
        # Indicates the next node should be assigned to this parent
        stack = [(root, True), (root, False)]
        
        for i in range(1, len(tokens)):
            token = tokens[i]
            
            if not stack:
                break
            
            parent, is_left = stack.pop()
            
            if token != self.NULL_MARKER:
                child = TreeNode(int(token))
                
                if is_left:
                    parent.left = child
                else:
                    parent.right = child
                
                # Push placeholders for this child's children
                # Note: Push right first so left is popped first
                stack.append((child, False))  # Placeholder for right child
                stack.append((child, True))   # Placeholder for left child
        
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def choose_deserializer(
    format: str,           # "preorder", "level_order", "json"
    trusted_input: bool,   # Is input from a trusted source?
    input_size: str,       # "small", "medium", "large"
    depth_bound: int,      # Maximum expected tree depth
    throughput: str        # "low", "high"
) -> str:
    """Guide for choosing deserialization approach."""
    
    if not trusted_input:
        return "ValidatedDeserializer with strict limits"
    
    if input_size == "large":
        return "StreamingDeserializer with buffered I/O"
    
    if depth_bound > 1000:
        return "IterativeDeserializer to avoid stack overflow"
    
    if throughput == "high":
        return "ScanningParser with object pooling"
    
    # Default: Simple recursive for readability
    return "RecursiveDescentDeserializer"