Python 0449.py
class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
tokens = []
def deeper(node):
nonlocal tokens
if node:
# preorder
tokens.append(str(node.val))
deeper(node.left)
deeper(node.right)
else:
tokens.append("")
deeper(root)
return "|".join(tokens)
def deserialize(self, data: str) -> Optional[TreeNode]:
tokens = data.split("|")
pos = 0
def deeper():
nonlocal pos, tokens
value = tokens[pos]
pos += 1
if value == "":
return None
else:
left = deeper()
right = deeper()
return TreeNode(int(value), left, right)
return deeper()
Difficulty
and has an acceptance rate of about 60% (400k+ submissions).
Typical patterns to solve this problem:
- Binary Search Tree
- Binary Tree
- Breadth First Search
- Depth First Search
- Design
- String
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Codec class implements a pair of complementary operations for binary trees: converting a tree into a single string representation (serialize) and rebuilding the original tree from that string (deserialize). Both methods rely on a depth-first traversal that records node values in preorder (root, left, right) while explicitly marking absent children. The string format uses the pipe character (|) as a delimiter, allowing a straightforward split during reconstruction.
Serialization Process
The serialize method begins by allocating an empty list called tokens. A nested helper function named deeper performs a recursive preorder walk of the tree. For each visited node, its value is converted to a string and appended to tokens. When the recursion encounters a None reference, an empty string ("") is appended instead, serving as a placeholder for a missing child. After the entire tree has been traversed, the list of tokens is collapsed into a single string using the pipe delimiter.
def serialize(self, root: Optional[TreeNode]) -> str:
tokens = []
def deeper(node):
nonlocal tokens
if node:
# preorder
tokens.append(str(node.val))
deeper(node.left)
deeper(node.right)
else:
tokens.append("")
deeper(root)
return "|".join(tokens)
Key aspects of this implementation include:
- The use of
nonlocalto give the inner function direct access to thetokenslist without passing it as an argument on each recursive call. - The explicit insertion of an empty string for
Nonenodes, which guarantees that the serialized form preserves the exact structure of the original tree, even when children are missing. - The final
joinoperation, which creates the output string in a single pass over the token list, avoiding repeated string concatenations that would be costly for large trees.
Deserialization Process
The deserialize method reverses the serialization logic. It first splits the incoming string on the pipe delimiter, producing the same sequence of tokens that were generated during serialization. A positional index pos tracks the current token being processed. A nested helper function deeper reads the token at pos, advances the index, and decides whether to create a new TreeNode or return None. If the token is an empty string, the function returns None, representing a missing child. Otherwise, it recursively constructs the left and right subtrees before instantiating a TreeNode with the integer value of the token.
def deserialize(self, data: str) -> Optional[TreeNode]:
tokens = data.split("|")
pos = 0
def deeper():
nonlocal pos, tokens
value = tokens[pos]
pos += 1
if value == "":
return None
else:
left = deeper()
right = deeper()
return TreeNode(int(value), left, right)
return deeper()
Important characteristics of this routine are:
- The
posvariable is shared across recursive calls vianonlocal, ensuring that each token is consumed exactly once in the order produced by the preorder traversal. - The function respects the placeholder empty strings, thereby reconstructing
Nonechildren precisely where they appeared in the original tree. - By converting the token to an integer only when a real node is created, the method avoids unnecessary parsing of placeholder entries.
Edge Cases Handled
The algorithm gracefully manages several boundary conditions without additional checks:
- Empty tree - When
rootisNone, theserializefunction records a single empty string token, resulting in an output of"". During deserialization, the split yields a list containing one empty string; the first call todeeperencounters this placeholder and returnsNone, correctly reconstructing an empty tree. - Single-node tree - The token list consists of the node’s value followed by two empty strings for its absent left and right children. The deserializer reads the value, creates the node, and then processes the two placeholders, yielding a tree with the correct solitary node.
- Trees with asymmetric structure - Because every
Nonechild is explicitly represented, trees that have left children without right children (or vice versa) are serialized with the appropriate empty placeholders. The deserializer’s recursive order matches the preorder layout, ensuring that each placeholder aligns with the correct side of its parent. - Trailing delimiters - The
joinoperation never produces a trailing pipe; however, even if the input string contained extra delimiters, thesplitmethod would generate additional empty tokens, each of which would be interpreted as aNonechild, preserving structural integrity.
Performance Optimizations
The implementation incorporates several choices that keep the runtime efficient for typical tree sizes:
- In-place token accumulation - By appending to a mutable list during traversal and performing a single
joinat the end, the code avoids the quadratic cost associated with repeated string concatenation. - Shared state via
nonlocal- Both helper functions capture the surrounding variables (tokensfor serialization,posandtokensfor deserialization) without the overhead of passing them as parameters on each recursive call. This reduces function call overhead and keeps the call stack lean. - Lazy parsing of values - The deserializer converts a token to an integer only when it is certain that the token represents a real node. This avoids unnecessary integer conversion for placeholder entries, which can be beneficial when the tree contains many null children.
- Single pass reconstruction - The recursive
deeperfunction consumes tokens sequentially, guaranteeing that each token is examined exactly once. There is no need for auxiliary data structures such as stacks or queues, which would add memory pressure.
Overall, the code delivers a compact and direct solution for binary tree serialization and deserialization, leveraging recursion and simple string operations to maintain both clarity and efficiency.
ELI5 - Simplified Explanation
Imagine you have a big, sprawling family tree built out of wooden blocks. Each block has a number written on it. To move these blocks from one room to another, you cannot carry the whole tree at once because it is too big. Instead, you have to take the tree apart piece by piece and put the pieces into a long, straight line.
The first part of the code works like a helper that walks through the tree. It visits every block one by one, starting at the top and following every branch. Every time it finds a block, it writes that number down on a piece of paper. If it finds an empty spot where a branch ends, it writes down an empty sign so it remembers that nothing belongs there. By the time it finishes, there is a long string of numbers and empty signs connected by little lines.
The second part of the code does the opposite job. It looks at the long string of symbols and starts building the tree from scratch. It reads the first item and places that block at the very top. Then, it uses the next items in line to figure out if it should build to the left or to the right. It keeps reading the symbols one by one, clicking the pieces together just like before, until every block is back in its right place and the tree is standing tall again just like it was at the beginning.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | Go | ||||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| MemoryLimitExceeded | C++ | Python | ||||||||
| Progiez | C++ | Python | Java | |||||||
| github | BigEggStudy | C# | ||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| haoel | Python | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| luangong | TS | |||||||||
| lzl124631x | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| yuanliu666 | Kotlin | |||||||||
| YuriSpiridonov | Python | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||
| Progiez | C++, Java, Python | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| haoel | Python | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| luangong | TypeScript | |||||||||
| lzl124631x | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| yuanliu666 | Kotlin | |||||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 428: Serialize and Deserialize N-ary Tree
Solved On The Same Day
- problem 1022: Sum of Root To Leaf Binary Numbers
- problem 1582: Special Positions in a Binary Matrix
- problem 2331: Evaluate Boolean Binary Tree
- problem 894: All Possible Full Binary Trees
- problem 919: Complete Binary Tree Inserter
- problem 951: Flip Equivalent Binary Trees
- problem 2415: Reverse Odd Levels of Binary Tree
- problem 297: Serialize and Deserialize Binary Tree
- problem 834: Sum of Distances in Tree
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality