Domain 2MediumCORE

Serialize and Deserialize BST

We need to convert a Binary Search Tree into a string representation that captures both the node values and the tree structure (shape), then reconstruct the exact same tree from that string later.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree

449. Serialize and Deserialize BST

Model: qwen3.5:9b
Topics: Tree
FAANG asked: 1
Acceptance rate: 54.3%


Problem Breakdown

We need to convert a Binary Search Tree into a string representation that captures both the node values and the tree structure (shape), then reconstruct the exact same tree from that string later.

Inputs: The root of a BST (TreeNode). Outputs: A serialized string, and upon deserialization, the original root pointer to the reconstructed tree.

Key Constraints & Edge Cases:

  1. Empty Tree: If input is empty (null), output should represent an empty structure.
  2. Structure Preservation: We cannot rely solely on values because multiple trees can have identical sets of node values but different shapes (e.g., a skewed tree vs. balanced). The serialization must encode the “shape” or explicitly mark missing children to ensure reconstruction is deterministic.
  3. Compactness: While we want it compact, correctness takes precedence over extreme optimization unless specified otherwise. However, using standard BFS with null markers avoids ambiguity without needing complex range checks during deserialization.
  4. Data Types: Node values are non-negative integers (0 to 10^4). This simplifies parsing (no negative signs).

Intuition

A brute-force approach might be storing the entire tree object directly, but we need a string format for transmission/storage.

If I simply store node values in an array without structure markers, I lose information about where branches end or begin. For example, [1] could mean root=1, left=null, right=null. But if I have [2, 3]`, is it root 2 with child 3 on the left? Or root 2 with child 3 on the right? Without markers for null children during traversal, we can’t distinguish.

Key Insight: We need a linear sequence that preserves both values and structure deterministically.

  1. Serialization (BFS): Level-order traversal is ideal here because it processes nodes level by level from left to right. When we encounter a missing child in the tree, we explicitly mark it as null in our string buffer. This ensures that when deserializing, if we see two consecutive nulls or specific patterns of non-null values following parents, we know exactly where branches terminate and new subtrees begin.
  2. Deserialization: We can parse this linear list using a queue (or an iterator). As we iterate through the tokens, whenever we encounter a valid number, we create a node and attach it to its parent’s left or right pointer based on traversal order.

While Preorder with markers is also possible, Level-Order maps directly to how binary trees are often represented in arrays (like LeetCode input format), making reconstruction logic very straightforward using an index/queue approach without needing recursive range checks. This keeps the implementation clean and robust (O(N)O(N)).

Approach

  1. Serialization:

    • Initialize a queue with the root node if it exists. If empty, return "[]" or similar indicator (I’ll use "" for consistency with list representation logic in Python context, but standard LC uses comma-separated string). Let’s stick to comma-separated values like "2,null,1".
    • Perform BFS: While the queue is not empty, pop a node. Append its value to our result list. If it has left/right children, push them; otherwise, append null placeholders for missing slots in that level?
    • Wait, standard optimization: Only enqueue existing nodes but track indices carefully? No, simpler logic: Enqueue root. While queue not empty: pop node -> add value to string list. If child exists, enqueue it and mark as valid; else append null placeholder for the missing slot in our conceptual level order stream.
    • Actually, standard BFS serialization adds children only if they exist? No, we need placeholders so deserialization knows where a branch ends.
    • Refined Logic: Use a queue of nodes to serialize. For every node popped: add value. If left child exists -> enqueue it; else append null placeholder (conceptually). Wait, standard approach is simpler: Just iterate through the tree level by level using a pointer or deque logic where we push children into a list and join them at end?
    • Simpler Implementation: Use an iterator over the string array during deserialization. For serialization, use collections.deque for BFS queue to handle levels efficiently.
  2. Deserialization:

    • Split the serialized string by delimiter (e.g., ,).
    • Create a dummy root or start with first token as actual root if not null.
    • Use an index pointer i.
    • Maintain two pointers: one for current parent (parent) and one for next child to attach (child_idx in the list). Or simpler: Reconstruct using BFS logic again on a queue of nodes created so far, iterating through tokens.
  3. Complexity: Both steps visit every node exactly once. String length is proportional to number of digits + delimiters ≈O(N)\approx O(N). Space for string and queues is O(N)O(N).

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes in the tree. We traverse each node once during serialization (BFS queue operations). During deserialization, we iterate through every token exactly once to create nodes and link them.
  • Space Complexity: O(N)O(N). The serialized string takes space proportional to total characters (≈N×5\approx N \times 5 chars per number on average + delimiters). We also use a Queue for BFS which holds up to N/2N/2 nodes in the worst case (last level), and recursion stack is not used here.

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root: 'TreeNode') -> str:
    if not root:
        return "" # Or "[]" depending on expected format. 
                  # Standard LC expects comma separated with nulls for structure.
    
    res = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        # Add value to result list (convert int to string)
        if node is not None:
            res.append(str(node.val))
            # Enqueue children. If child exists, add it; else we don't strictly need 
            # a placeholder in the BFS logic for serialization IF we handle deserialization carefully?
            # Actually, standard approach requires placeholders to know where tree ends.
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        else:
             res.append("null")

    return ",".join(res)

def deserialize(data: str) -> 'TreeNode':
    if not data or len(data.strip()) == 0: # Handle empty string case carefully based on serialize logic above
         return None
    
    vals = iter(data.split(","))
    
    root_val = next(vals, None)
    if root_val is None: 
        return None
        
    root = TreeNode(int(root_val))
    queue = deque([root])
    
    while True:
        try:
            # We need to process the current parent's children from vals iterator.
            # But we can't easily peek at next two values without consuming them?
            # Better approach for deserialization with BFS logic on list of tokens:
            
            pass 
        except StopIteration:
            break
            
    return root

# Re-writing deserialize to be cleaner using index pointer over split list
def deserialize_clean(data):
    if not data or len(data.strip()) == 0: # Assuming serialize returns empty string for null tree? Or "[]"?
       # Let's assume standard LC behavior where [] is input, but serialization usually uses comma separated. 
       # If root is None -> return "" (empty). But example says Input: [], Output [].
       # I will handle the case where data represents an empty list or string representation of nulls.
       
    vals = [int(x) if x != 'null' else None for x in data.split(',')]
    
    root = TreeNode(vals[0])
    queue = deque([root])
    idx = 1
    
    while queue and idx < len(vals):
        node = queue.popleft()
        
        # Left child
        if vals[idx] is not None:
            left_node = TreeNode(vals[idx])
            node.left = left_node
            queue.append(left_node)
        idx += 1
        
        # Right child (if exists in list and we haven't exhausted it)
        if idx < len(vals):
             if vals[idx] is not None:
                right_node = TreeNode(vals[idx])
                node.right = right_node
                queue.append(right_node)
            idx += 1
            
    return root

# Wait, the serialize logic above doesn't add 'null' placeholders for missing children in a skewed tree? 
# If I have [2] -> left=null. My loop: pop 2. append "2". enqueue nothing (since no child). 
# Result string "2". Deserialization reads "2", creates root, idx=1. Loop ends because queue empty and vals exhausted.
# This works for skewed trees ONLY IF we don't need to know where the missing children are? 
# Actually, if I have [2] -> right=null (skewed left), BFS logic: pop 2. append "2". enqueue nothing. 
# If tree is root=1, right=3. Pop 1. Append "1". Enqueue 3. Next iter pop 3.
# String becomes "1,null,3" if I add nulls for missing children? Or just "1,3"?
# Standard LC solution requires explicit 'null' markers to distinguish between [2] and [2->right=3]. 
# If string is "1", it implies no right child. But how do we know 3 isn't a sibling of something else later?
# In BFS serialization: We MUST add nulls for missing children so the deserializer knows where branches end in level order.

Correction on Serialization Logic: To ensure reconstruction is unique, if I have root=1, left=null, right=3 (skewed). Level Order traversal visits 1. Then it must visit its children slots: Left(null), Right(3). So the queue logic should be: Pop node -> Add value to list. If child exists push to queue; else do NOT push? If I don’t push null for missing children, my string is just values of existing nodes in BFS order. Example: Root 1 (L=null), Right 3. Queue: [1]. Pop 1 -> List=[1]. Push nothing? Then queue empty. String=“1”. Deserialization reads “1”, creates root. Loop ends. Tree is just 1. We lost node 3. Therefore: I must push placeholders for missing children into the conceptual stream, OR use a different traversal (Preorder with markers). However, standard LC solution usually iterates through levels and adds nulls to represent empty slots in that level? Actually, simpler logic: Use BFS queue. When popping node u, if left child exists -> push it; else append ‘null’ placeholder conceptually but don’t enqueue a dummy object for the next iteration of loop unless we are tracking indices strictly. Best Practice: Serialize using Preorder with explicit nulls? Or Level Order where you track children slots in queue? Let’s use Level-Order BFS but ensure that if node has no left child, we append ‘null’ to our list and do NOT enqueue a dummy node for it. But wait, how does the deserializer know which parent corresponds to which nulls? The standard way: Queue stores nodes to be visited.

  1. Enqueue root.
  2. While queue not empty: Pop u. Add value of u (or ‘null’ if u is dummy). If left child exists, enqueue it; else append ‘null’. Same for right. Wait, this mixes logic.

Correct Standard Logic: Use a list to store the serialized values in BFS order. Use a queue to track nodes to be processed.

  1. queue = [root] (if root).

  2. While queue: pop u. Add u.val or ‘null’ if u is None? No, we only push valid nodes into the processing queue initially. But for serialization string construction: We need to represent missing children as nulls in the output list so deserialization knows where branches end. Actually, most efficient way: Iterate through levels using a pointer i on result array vs current level size? No, simpler:

    q = deque([root])
    res = []
    while q:
        u = q.popleft()
        if u is None: # This shouldn't happen in standard BFS queue unless we push nulls
            res.append('null') 
            continue
        
        res.append(str(u.val))
        q.append(u.left)  # Push left (even if None? No, usually don't push None to avoid infinite loop or complexity?)

    Let’s stick to the most robust method: Preorder with explicit nulls. Why? Because it maps perfectly to a recursive structure and is easier to implement without queue management errors in an interview setting (no need for level tracking). But Level Order is requested often because of “array representation”.

    Let’s go back to Level-Order but handle the null insertion correctly. We process nodes that exist. If a node has no left child, we record ‘null’ in our list and do not add anything to queue? No, if we don’t add nulls to queue, deserializer won’t know about them later levels.

    Correct Logic for Level-Order Serialization: We need the output string to represent a complete binary tree structure where missing nodes are null.

    1. Initialize list with root value (if exists).
    2. Use queue of indices or just process existing nodes? Actually, simpler: Just use Preorder traversal and append ‘null’ for every None child encountered during recursion/iteration. This is O(N)O(N) space/time too.

    Decision: I will implement Level-Order but ensure that when we encounter a missing child in the tree structure (during BFS), we add None to our result list? No, standard LC solution uses:

    q = deque([root])
    while q:
        u = q.popleft()
        if not u: # If queue contains nulls representing missing children
             res.append("null") 
             continue
        res.append(str(u.val))
        q.append(u.left)
        q.append(u.right)

    This works! We push u.left and u.right regardless of whether they exist. If a child is None, we append “null” to result list (via the check inside loop or after). Wait, if I pop null from queue?

    Refined Code Plan:

    1. Serialize: BFS Queue containing nodes. When popping u: add value. Push left/right children into queue even if they are None. This ensures we process all slots in level order including missing ones (which appear as ‘null’ when popped). Wait, pushing Nones to the queue means we iterate through them later and append “null”. Yes, this works perfectly for reconstruction because deserialization will see a sequence of values where None indicates no node exists at that position in the level-order array.

    2. Deserialize: Split string by ,. Use an iterator or index to read tokens. Maintain a queue of nodes created so far (excluding nulls). For each token, if not ‘null’, create TreeNode and attach it as left/right child of current parent pointer? Actually simpler deserialization logic for Level-Order array [v1, v2, v3...]:

      • Create root from first value. Enqueue root to q.
      • Iterate through remaining tokens with index i (starting at 0 relative to list).
      • Pop parent from queue? No, we need two pointers: one for current node being processed as a child of the previous level’s nodes.

    Simpler Deserialization Logic: Use an iterator over values. Create root if first value is not null. Enqueue it to q. While q has items and we have tokens left: Pop parent from queue? No, that loses the link between levels easily without tracking parents explicitly.

    Better Deserialization Logic: Use a pointer i over values list (skipping root). Maintain an index for next child to attach (child_idx). Iterate through nodes created so far in BFS order and assign left/right children from tokens at child_idx. Increment pointers appropriately.

Edge Cases Handled

  • Empty Tree: If input is empty, serialize returns empty string or specific marker; deserialize handles this by returning None immediately if data is empty/invalid.
  • Single Node: BFS queue processes root, pushes two nulls (conceptually), deserialization attaches children correctly as missing.
  • Skewed Trees: The explicit null placeholders in the serialized string ensure that a right-skewed tree doesn’t get confused with a left-skewed one or an empty list during reconstruction.

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root: 'TreeNode') -> str:
    if not root:
        return "" # Represents empty tree
    
    res = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if node is None:
            res.append("null")
            continue
            
        res.append(str(node.val))
        queue.append(node.left)  # Push left child (could be None)
        queue.append(node.right) # Push right child (could be None)
    
    return ",".join(res)

def deserialize(data: str) -> 'TreeNode':
    if not data or len(data.strip()) == 0:
        return None
    
    vals = iter(data.split(","))
    
    try:
        root_val = next(vals, None) # Get first value
        if root_val is None: 
            return None
            
        root = TreeNode(int(root_val))
        
        queue = deque([root])
        
        while True:
            node = queue.popleft()
            
            left_child_str = next(vals, None)
            right_child_str = next(vals, None) # Peek or consume? We must consume.
            
            if left_child_str is not None and left_child_str != "null":
                left_node = TreeNode(int(left_child_str))
                node.left = left_node
                queue.append(left_node)
                
            if right_child_str is not None and right_child_str != "null":
                right_node = TreeNode(int(right_child_str))
                node.right = right_node
                queue.append(right_node)
            
            # If we ran out of tokens, break. 
            # But next() raises StopIteration which needs handling or check before calling?
            # Using try/except block for cleaner iteration logic
            
    except StopIteration:
        pass
        
    return root

# Refining deserialize to be robust against partial reads (though problem guarantees valid input)
def deserialize_optimized(data):