How hard is LeetCode 449. Serialize and Deserialize BST?

LeetCode 449. Serialize and Deserialize BST is rated Medium on LeetCode.

What is the time complexity of LeetCode 449. Serialize and Deserialize BST?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 449. Serialize and Deserialize BST?

The Python solution on this page uses O(V) auxiliary space.

Serialize and Deserialize BST — LeetCode 449 Python Solution

MediumTreeDepth-First SearchBreadth-First SearchDesignBinary Search TreeStringBinary Tree

Problem: #449
Pattern: Tree Traversal
Reading time: 8 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""

        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            nums.append(root.val)
            dfs(root.left)
            dfs(root.right)

        nums = []
        dfs(root)
        return " ".join(map(str, nums))

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""

        def dfs(mi: int, mx: int) -> Optional[TreeNode]:
            nonlocal i
            if i == len(nums) or not mi <= nums[i] <= mx:
                return None
            x = nums[i]
            root = TreeNode(x)
            i += 1
            root.left = dfs(mi, x)
            root.right = dfs(x, mx)
            return root

        nums = list(map(int, data.split()))
        i = 0
        return dfs(-inf, inf)


# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 449. Serialize and Deserialize BST is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 449. Serialize and Deserialize BST?: LeetCode 449. Serialize and Deserialize BST is rated Medium on LeetCode.
What is the time complexity of LeetCode 449. Serialize and Deserialize BST?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 449. Serialize and Deserialize BST?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 449. Serialize and Deserialize BST cover?: LeetCode 449. Serialize and Deserialize BST is tagged Tree, Depth-First Search, Breadth-First Search, Design, Binary Search Tree, String and Binary Tree on LeetCode.