Golang BFS solution O(n)
\ntype Codec struct {\n}\n\nfunc Constructor() Codec {\n    return Codec{}\n}\n\nfunc (this *Codec) serialize(root *TreeNode) string {\n    var queue []*TreeNod
```\ntype Codec struct {\n}\n\nfunc Constructor() Codec {\n    return Codec{}\n}\n\nfunc (this *Codec) serialize(root *TreeNode) string {\n    var queue []*TreeNode\n\n\tenqueue(&queue, root)\n\n\tvar result string\n\n\tfor len(queue) > 0 {\n\t\tdequeuedElement := dequeue(&queue)\n\n\t\tif dequeuedElement != nil {\n\t\t\tresult = result + fmt.Sprintf("%v", dequeuedElement.Val) + ","\n\t\t\tenqueue(&queue, dequeuedElement.Left)\n\t\t\tenqueue(&queue, dequeuedElement.Right)\n\t\t} else {\n\t\t\tresult = result + "nil" + ","\n\t\t}\n\t}\n\n\treturn result[:len(result)-1]\n}\n\nfunc (this *Codec) deserialize(data string) *TreeNode {    \n    splittedData := strings.Split(data, ",")\n\n\tvar result []*TreeNode\n\n\tfor _, num := range splittedData {\n\t\tif num == "nil" {\n\t\t\tresult = append(result, nil)\n\t\t} else {\n\t\t\titem := TreeNode{\n\t\t\t\tVal: toInt(num),\n\t\t\t}\n\n\t\t\tresult = append(result, &item)\n\t\t}\n\t}\n    \n    begin := 0\n    \n\tfor _, node := range result {\n\t\tif node == nil {\n            continue\n\t\t} else {\n\t\t\tleft := 2 * begin + 1\n\t\t\tright := 2 * begin + 2\n\n\t\t\tif left < len(result) {\n\t\t\t\tnode.Left = result[left]\n\t\t\t}\n\n\t\t\tif right < len(result) {\n\t\t\t\tnode.Right = result[right]\n\t\t\t}\n            \n            begin++\n\t\t}\n\t}\n\n\treturn result[0]\n}\n\nfunc enqueue(queue *[]*TreeNode, newItem *TreeNode) {\n\tif queue == nil {\n\t\tpanic("nil pointer")\n\t}\n\n\t*queue = append(*queue, newItem)\n}\n\nfunc dequeue(queue *[]*TreeNode) *TreeNode {\n\tif queue == nil {\n\t\tpanic("nil pointer")\n\t}\n\n\tif len(*queue) == 0 {\n\t\tpanic("empty queue")\n\t}\n\n\tdequeuedElement := (*queue)[0]\n\n\t*queue = (*queue)[1:len(*queue)]\n\n\treturn dequeuedElement\n}\n\nfunc toInt(s string) int {\n\tvalue, err := strconv.Atoi(s)\n\n\tif err != nil {\n\t\tpanic(err)\n\t}\n\n\treturn value\n}\n```
['Breadth-First Search', 'Go']