C++ Truly O(n) solution using BFS with explanation
Can also be used to optimally solve https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/\n\nUnlike many solutions posted, this is a 
Can also be used to optimally solve https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/\n\nUnlike many solutions posted, this is a truly O(n) solution. Basically we are seralize and deserializing using BFS or level-by-level traversal.\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Codec {\npublic:\n    // Encodes a tree to a single string.\n    string serialize(TreeNode* root) {\n        if (root == nullptr) return "";\n        string ans = "";\n        queue<TreeNode*> bfsQueue;\n        bfsQueue.push(root);\n        while (!bfsQueue.empty()) {\n            TreeNode* curr = bfsQueue.front();\n            bfsQueue.pop();\n            if (curr == nullptr) ans += "# ";\n            else {\n                ans += std::to_string(curr->val) + " ";\n                bfsQueue.push(curr->left);\n                bfsQueue.push(curr->right);\n            }\n        }\n        return ans;\n    }\n\n    // Decodes your encoded data to tree.\n    TreeNode* deserialize(string data) {\n        vector<string> vals;\n        string curr = "";\n        for (char v: data) {\n            if (v == \' \') {\n                if (curr != "") {\n                    vals.push_back(curr);\n                    curr = "";\n                }\n            } else {\n                curr += v;\n            }\n        }\n        if (vals.empty()) return nullptr;\n\n        TreeNode* root = new TreeNode(std::stoi(vals[0]));\n        queue<TreeNode*> bfsQueue;\n        bfsQueue.push(root);\n        int index = 1;\n        while (!bfsQueue.empty()) {\n            TreeNode* curr = bfsQueue.front();\n            bfsQueue.pop();\n\n            // process left\n            string left = vals[index];\n            ++index;\n            if (left == "#") {\n                curr->left = nullptr;\n            } else {\n                TreeNode* newNode = new TreeNode(std::stoi(left));\n                curr->left = newNode;\n                bfsQueue.push(newNode);\n            }\n\n            // process right\n            string right = vals[index];\n            ++index;\n            if (right == "#") {\n                curr->right = nullptr;\n            } else {\n                TreeNode* newNode = new TreeNode(std::stoi(right));\n                curr->right = newNode;\n                bfsQueue.push(newNode);\n            }\n        }\n\n        return root;\n    }\n};\n\n// Your Codec object will be instantiated and called as such:\n// Codec* ser = new Codec();\n// Codec* deser = new Codec();\n// string tree = ser->serialize(root);\n// TreeNode* ans = deser->deserialize(tree);\n// return ans;\n```
['C++']