A basic binary tree deserializer: parses a binary tree structure from an input string like: (5(3(2(-123)())(4))(7(6)(9(8)())))

main.go

package main

import (
	"bytes"
	"errors"
	"fmt"
	"reflect"
	"strconv"
	"strings"
)

type TreeNode struct {
	value       int
	left, right *TreeNode
}

func (t *TreeNode) Serialize() string {
	var out bytes.Buffer
	out.WriteRune('(')
	if t != nil {
		if t.isLeaf() {
			out.WriteString(fmt.Sprintf("%d", t.value))
		} else {
			out.WriteString(fmt.Sprintf("%d%s%s",
				t.value, t.left.Serialize(), t.right.Serialize()))
		}
	}
	out.WriteRune(')')
	return out.String()
}

func (t *TreeNode) isLeaf() bool {
	return t.left == nil && t.right == nil
}

const (
	LBRACE = '('
	RBRACE = ')'
)

type Parser struct {
	reader     *strings.Reader
	pos        int
	curr, next rune
	hasNext    bool
}

func NewParser(reader *strings.Reader) (*Parser, error) {
	p := &Parser{
		reader: reader,
	}
	if err := p.Next(); err != nil {
		return nil, err
	}
	p.pos = 0
	return p, nil
}

func (p *Parser) Next() error {
	p.curr = p.next
	next, _, err := p.reader.ReadRune()
	if err != nil {
		return err
	}
	p.next = next
	p.hasNext = p.reader.Len() > 0
	p.pos++
	return nil
}

func (p *Parser) HasNext() bool {
	return p.hasNext
}

func (p *Parser) Peek() rune {
	return p.next
}

func (p *Parser) Curr() rune {
	return p.curr
}

func (p *Parser) Parse() (*TreeNode, error) {
	return p.readNode()
}

func (p *Parser) readNode() (*TreeNode, error) {
	if p.Peek() != LBRACE {
		return nil, errors.New(fmt.Sprintf(
			"unexpected symbol at index: %d", p.pos))
	}
	p.Next()
	if p.Peek() == RBRACE {
		p.Next()
		// The node is empty
		return nil, nil
	}
	p.Next()
	node := &TreeNode{}
	if value, err := p.readLiteral(); err != nil {
		return nil, err
	} else {
		node.value = value
	}
	p.eatWhitespace()
	if p.Peek() == RBRACE {
		// The node is a leaf
		p.Next()
		return node, nil
	}
	if left, err := p.readNode(); err != nil {
		return nil, err
	} else {
		node.left = left
	}
	p.eatWhitespace()
	if right, err := p.readNode(); err != nil {
		return nil, err
	} else {
		node.right = right
	}
	if p.Peek() != RBRACE {
		return nil, errors.New(fmt.Sprintf(
			"missing closing brace at pos: %d", p.pos))
	}
	p.Next()
	return node, nil
}

func (p *Parser) readLiteral() (int, error) {
	var b bytes.Buffer
	for p.HasNext() {
		b.WriteRune(p.Curr())
		if peek := p.Peek(); peek != '-' && !isDigit(peek) {
			break
		}
		p.Next()
	}
	return strconv.Atoi(b.String())
}

func isDigit(r rune) bool {
	return r >= '0' && r <= '9'
}

func (p *Parser) eatWhitespace() {
	for p.HasNext() && p.Peek() == ' ' {
		p.Next()
	}
}

func main() {
	tree := &TreeNode{
		value: 5,
		left: &TreeNode{
			value: 3,
			left: &TreeNode{
				value: 2,
				left: &TreeNode{
					value: -123,
				},
			},
			right: &TreeNode{
				value: 4,
			},
		},
		right: &TreeNode{
			value: 7,
			left: &TreeNode{
				value: 6,
			},
			right: &TreeNode{
				value: 9,
				left: &TreeNode{
					value: 8,
				},
			},
		},
	}

	srlzd := tree.Serialize()
	fmt.Println(srlzd)

	p, err := NewParser(strings.NewReader(srlzd))
	if err != nil {
		panic(err.Error())
	}
	parsedTree, err := p.Parse()
	if err != nil {
		panic(err.Error())
	}
	if !reflect.DeepEqual(tree, parsedTree) {
		panic(fmt.Sprintf("tree structures are distinct:\ngot= %#v\nwant=%#v",
			tree.Serialize(), parsedTree.Serialize()))
	}
}