A somewhat obvious solution is to emulate a heap and replace the missing nodes with "x" markers, but this performs badly on path trees (only left links). An improvement would be to replace consecutive "x"-es by "x<number>", where number==how many x-es are replaced. The solution in this gist does a depth-first traversal and prints the tree recurs…

tree-ser-deser.go

package main

import (
	"fmt"
	"math/rand"
	"strconv"
	"strings"
	"time"
)

type node struct {
	l, r *node
	val  int
}

func Serialize(n *node) string {
	if n == nil {
		return ""
	}
	out := fmt.Sprint(n.val)
	if n.l == nil && n.r == nil {
		return out
	}
	out += "("
	if n.l != nil {
		out += Serialize(n.l)
	} else {
		out += "x"
	}
	out += " "
	if n.r != nil {
		out += Serialize(n.r)
	} else {
		out += "x"
	}
	return out + ")"
}

func Deserialize(s string) *node {
	out := new(node)
	helper(Tokenize(s), out, false)
	return out.l
}

// adds a new node (or nil) to ((isRight) ? prev.r : prev.r)
// max stack is O(h), h ∈ [logn, n]
func helper(s []string, prev *node, isRight bool) []string {
	if len(s) < 1 {
		return s
	}
	var tmp *node = new(node)
	if val, err := strconv.Atoi(s[0]); err == nil {
		tmp.val = val
		s = s[1:]
	} else if strings.ToLower(s[0]) == "x" {
		return s[1:]
	} else {
		panic("bad format") // expected int or "x"
	}
	if isRight {
		prev.r = tmp
	} else {
		prev.l = tmp
	}
	if len(s) < 1 || s[0] != "(" {
		return s
	}
	s = helper(s[1:], tmp, false)
	s = helper(s, tmp, true)
	if len(s) < 1 || s[0] != ")" {
		panic("bad format")
	}
	return s[1:]
}

const WS = " \t\n"

// simply turns a string into an array of ints, parens, and "x"-es
func Tokenize(s string) []string {
	out := []string{}
	for len(s) > 0 {
		// skipping whitespace
		for len(s) > 0 && strings.ContainsRune(WS, rune(s[0])) {
			s = s[1:]
		}
		tmp := ""
		for len(s) > 0 && !strings.ContainsRune(WS, rune(s[0])) {
			if strings.ContainsRune("()", rune(s[0])) {
				if len(tmp) == 0 {
					tmp = string(s[0])
					s = s[1:]
				}
				break
			}
			tmp += string(s[0])
			s = s[1:]

		}
		if len(tmp) > 0 {
			out = append(out, tmp)
		}
	}
	return out
}

func RandTree(n int) *node {
	if n == 0 {
		return nil
	}
	tmp := new(node)
	tmp.val = rand.Intn(99) + 1
	cut := rand.Intn(n)
	tmp.l = RandTree(cut)
	tmp.r = RandTree(n - 1 - cut)
	return tmp
}

func PrintTree(n *node, indent int) {
	fmt.Print(strings.Repeat("└-", indent))
	if n == nil {
		fmt.Println("x")
		return
	} else {
		fmt.Println(n.val)
	}
	if n.l == nil && n.r == nil {
		return
	}
	PrintTree(n.l, indent+1)
	PrintTree(n.r, indent+1)
}

func init() {
	rand.Seed(time.Now().UnixNano())
}

func main() {
	orig := RandTree(10)
	PrintTree(orig, 0)
	fmt.Println(Serialize(orig))
	clone := Deserialize(Serialize(orig))
	PrintTree(clone, 0)
	fmt.Println(Serialize(clone))
}