Level-order traversal also works!
We can use a queue to do a BFS, and encode the values in the order of nodes visited during BFS.\n\nWhen decoding, just insert the values back in that order with
We can use a queue to do a BFS, and encode the values in the order of nodes visited during BFS.\n\nWhen decoding, just insert the values back in that order with BST insertion, building the tree level by level. \n\nThe time complexity for reconstruction is O(n*log(n)), though, slightly worse than O(n) best case.\n\n```\nclass Codec:\n    def serialize(self, root: TreeNode) -> str:\n        if not root:\n            return \'\'\n        ans = []\n        q = collections.deque([root])\n        while q:  # BFS\n            node = q.popleft()\n            ans.append(node.val)\n            if node.left:\n                q.append(node.left)\n            if node.right:\n                q.append(node.right)\n        return \',\'.join([str(v) for v in ans[::-1]])  # reverse order so that when decoding, popping from the back takes O(1)\n\n    def deserialize(self, data: str) -> TreeNode:\n        if not data:\n            return None\n        data = [int(s) for s in data.split(\',\')]\n        root = TreeNode(data.pop())\n        \n        def insert(node, v):\n            left = True if v < node.val else False\n            if left:\n                if not node.left:\n                    node.left = TreeNode(v)\n                else:\n                    insert(node.left, v)  # recursively insert\n            else:\n                if not node.right:\n                    node.right = TreeNode(v)\n                else:\n                    insert(node.right, v)  # recursively insert\n        \n        while data:\n            insert(root, data.pop())  # insert the value into the tree\n            \n        return root\n```
['Python']