Problem 449

Abstract / Summary

Design methods to convert a binary search tree into a string and recreate the tree from that string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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()
33 lines | 888 bytes | submitted December 13, 2023 | GitHub   3% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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 nonlocal to give the inner function direct access to the tokens list without passing it as an argument on each recursive call.
  • The explicit insertion of an empty string for None nodes, which guarantees that the serialized form preserves the exact structure of the original tree, even when children are missing.
  • The final join operation, 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 pos variable is shared across recursive calls via nonlocal, 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 None children 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 root is None, the serialize function 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 to deeper encounters this placeholder and returns None, 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 None child 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 join operation never produces a trailing pipe; however, even if the input string contained extra delimiters, the split method would generate additional empty tokens, each of which would be interpreted as a None child, 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 join at the end, the code avoids the quadratic cost associated with repeated string concatenation.
  • Shared state via nonlocal - Both helper functions capture the surrounding variables (tokens for serialization, pos and tokens for 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 deeper function 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.26 | σ = 1.17

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
37 links | 24 authors | 9 languages

Videos

11 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

10 solutions   December 13, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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