Serialize and Deserialize BST

LeetCode 449 | Difficulty: Medium

Medium

Problem Description

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

- The number of nodes in the tree is in the range `[0, 10^4]`.

- `0 <= Node.val <= 10^4`

- The input tree is **guaranteed** to be a binary search tree.

Topics: String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Search Tree, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	42.9 MB
Date	2022-01-12

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

   // Encodes a tree to a single string.
        public string serialize(TreeNode root)
    {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.ToString();
        
    }
    
    private void serialize(TreeNode root, StringBuilder sb)
    {
        if (root == null)
        {
            sb.Append("#,");
            return;
        }
        sb.Append($"{root.val},");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        Queue<string> q = new Queue<string>(data.Split(new char[] { ','}, StringSplitOptions.RemoveEmptyEntries));
        return deserialize(q);
    }
    
    public TreeNode deserialize(Queue<string> q)
    {
        if(q.Count ==0 ) return null;
        var popped = q.Dequeue();
        if(popped == "#") return null;
        TreeNode root = new TreeNode(Convert.ToInt32(popped));
        root.left = deserialize(q);
        root.right = deserialize(q);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

📜 2 more C# submission(s)

Submission (2022-01-12) — 100 ms, 42.4 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

   // Encodes a tree to a single string.

    public string serialize(TreeNode root)
    {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.ToString();
        
    }

    private void serialize(TreeNode root, StringBuilder sb)
    {
        if (root == null)
        {
            return;
        }
        sb.Append($"{root.val},");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    private void serializeBT(TreeNode root, StringBuilder sb)
    {
        if (root == null)
        {
            sb.Append("#,");
            return;
        }
        sb.Append($"{root.val},");
        serializeBT(root.left, sb);
        serializeBT(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        Queue<string> q = new Queue<string>(data.Split(new char[] { ','}, StringSplitOptions.RemoveEmptyEntries));
        return deserialize(q, Int32.MinValue, Int32.MaxValue);
    }
    
    public TreeNode deserialize(Queue<string> q, int lower, int upper)
    {
        if(q.Count == 0) return null;
        var val = Convert.ToInt32(q.Peek());
        if(val < lower || val > upper) return null;
        q.Dequeue();
        TreeNode root = new TreeNode(val);
        root.left = deserialize(q, lower, val);
        root.right = deserialize(q, val, upper);
        return root; 
    }
    
    public TreeNode deserialize(Queue<string> q)
    {
        if(q.Count ==0 ) return null;
        var popped = q.Dequeue();
        if(popped == "#") return null;
        TreeNode root = new TreeNode(Convert.ToInt32(popped));
        root.left = deserialize(q);
        root.right = deserialize(q);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Submission (2020-01-27) — 116 ms, 31.6 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

   // Encodes a tree to a single string.
    public string serialize(TreeNode root)
    {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.ToString();       
    }
    
    private void serialize(TreeNode root, StringBuilder sb)
    {
        if(root == null)
        {
            sb.Append("#,");
            return;
        }
        sb.Append($"{root.val},");
        serialize(root.left, sb);
        serialize(root.right, sb);
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        Queue<string> q = new Queue<string>(data.Split(new char[] { ','}, StringSplitOptions.RemoveEmptyEntries));
        return deserialize(q);
    }
    
    public TreeNode deserialize(Queue<string> q)
    {
        if(q.Count == 0) return null;
        string s = q.Dequeue();
        if(s=="#") return null;
        TreeNode root = new TreeNode(int.Parse(s));
        root.left = deserialize(q);
        root.right = deserialize(q);
        return root;
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Clarify the expected time complexity for each operation before choosing data structures.