# exklamationmark's solution

## to Tree Building in the Go Track

Published at Aug 22 2018 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

Refactor a tree building algorithm.

Some web-forums have a tree layout, so posts are presented as a tree. However the posts are typically stored in a database as an unsorted set of records. Thus when presenting the posts to the user the tree structure has to be reconstructed.

Your job will be to refactor a working but slow and ugly piece of code that implements the tree building logic for highly abstracted records. The records only contain an ID number and a parent ID number. The ID number is always between 0 (inclusive) and the length of the record list (exclusive). All records have a parent ID lower than their own ID, except for the root record, which has a parent ID that's equal to its own ID.

An example tree:

``````root (ID: 0, parent ID: 0)
|-- child1 (ID: 1, parent ID: 0)
|    |-- grandchild1 (ID: 2, parent ID: 1)
|    +-- grandchild2 (ID: 4, parent ID: 1)
+-- child2 (ID: 3, parent ID: 0)
|    +-- grandchild3 (ID: 6, parent ID: 3)
+-- child3 (ID: 5, parent ID: 0)
``````

## Running the tests

To run the tests run the command `go test` from within the exercise directory.

If the test suite contains benchmarks, you can run these with the `--bench` and `--benchmem` flags:

``````go test -v --bench . --benchmem
``````

Keep in mind that each reviewer will run benchmarks on a different machine, with different specs, so the results from these benchmark tests may vary.

## Further information

For more detailed information about the Go track, including how to get help if you're having trouble, please visit the exercism.io Go language page.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### tree_test.go

``````package tree

import (
"fmt"
"math/rand"
"reflect"
"testing"
)

// Define a function Build(records []Record) (*Node, error)
// where Record is a struct containing int fields ID and Parent
// and Node is a struct containing int field ID and []*Node field Children.

var successTestCases = []struct {
name     string
input    []Record
expected *Node
}{
{
name:     "empty input",
input:    []Record{},
expected: nil,
},
{
name: "one node",
input: []Record{
{ID: 0},
},
expected: &Node{
ID: 0,
},
},
{
name: "three nodes in order",
input: []Record{
{ID: 0},
{ID: 1, Parent: 0},
{ID: 2, Parent: 0},
},
expected: &Node{
ID: 0,
Children: []*Node{
{ID: 1},
{ID: 2},
},
},
},
{
name: "three nodes in reverse order",
input: []Record{
{ID: 2, Parent: 0},
{ID: 1, Parent: 0},
{ID: 0},
},
expected: &Node{
ID: 0,
Children: []*Node{
{ID: 1},
{ID: 2},
},
},
},
{
name: "more than two children",
input: []Record{
{ID: 3, Parent: 0},
{ID: 2, Parent: 0},
{ID: 1, Parent: 0},
{ID: 0},
},
expected: &Node{
ID: 0,
Children: []*Node{
{ID: 1},
{ID: 2},
{ID: 3},
},
},
},
{
name: "binary tree",
input: []Record{
{ID: 5, Parent: 1},
{ID: 3, Parent: 2},
{ID: 2, Parent: 0},
{ID: 4, Parent: 1},
{ID: 1, Parent: 0},
{ID: 0},
{ID: 6, Parent: 2},
},
expected: &Node{
ID: 0,
Children: []*Node{
{
ID: 1,
Children: []*Node{
{ID: 4},
{ID: 5},
},
},
{
ID: 2,
Children: []*Node{
{ID: 3},
{ID: 6},
},
},
},
},
},
{
name: "unbalanced tree",
input: []Record{
{ID: 5, Parent: 2},
{ID: 3, Parent: 2},
{ID: 2, Parent: 0},
{ID: 4, Parent: 1},
{ID: 1, Parent: 0},
{ID: 0},
{ID: 6, Parent: 2},
},
expected: &Node{
ID: 0,
Children: []*Node{
{
ID: 1,
Children: []*Node{
{ID: 4},
},
},
{
ID: 2,
Children: []*Node{
{ID: 3},
{ID: 5},
{ID: 6},
},
},
},
},
},
}

var failureTestCases = []struct {
name  string
input []Record
}{
{
name: "root node has parent",
input: []Record{
{ID: 0, Parent: 1},
{ID: 1, Parent: 0},
},
},
{
name: "no root node",
input: []Record{
{ID: 1, Parent: 0},
},
},
{
name: "duplicate node",
input: []Record{
{ID: 0, Parent: 0},
{ID: 1, Parent: 0},
{ID: 1, Parent: 0},
},
},
{
name: "duplicate root",
input: []Record{
{ID: 0, Parent: 0},
{ID: 0, Parent: 0},
},
},
{
name: "non-continuous",
input: []Record{
{ID: 2, Parent: 0},
{ID: 4, Parent: 2},
{ID: 1, Parent: 0},
{ID: 0},
},
},
{
name: "cycle directly",
input: []Record{
{ID: 5, Parent: 2},
{ID: 3, Parent: 2},
{ID: 2, Parent: 2},
{ID: 4, Parent: 1},
{ID: 1, Parent: 0},
{ID: 0},
{ID: 6, Parent: 3},
},
},
{
name: "cycle indirectly",
input: []Record{
{ID: 5, Parent: 2},
{ID: 3, Parent: 2},
{ID: 2, Parent: 6},
{ID: 4, Parent: 1},
{ID: 1, Parent: 0},
{ID: 0},
{ID: 6, Parent: 3},
},
},
{
name: "higher id parent of lower id",
input: []Record{
{ID: 0},
{ID: 2, Parent: 0},
{ID: 1, Parent: 2},
},
},
}

func (n Node) String() string {
return fmt.Sprintf("%d:%s", n.ID, n.Children)
}

func TestMakeTreeSuccess(t *testing.T) {
for _, tt := range successTestCases {
actual, err := Build(tt.input)
if err != nil {
var _ error = err
t.Fatalf("Build for test case %q returned error %q. Error not expected.",
tt.name, err)
}
if !reflect.DeepEqual(actual, tt.expected) {
t.Fatalf("Build for test case %q returned %s but was expected to return %s.",
tt.name, actual, tt.expected)
}
}
}

func TestMakeTreeFailure(t *testing.T) {
for _, tt := range failureTestCases {
actual, err := Build(tt.input)
if err == nil {
t.Fatalf("Build for test case %q returned %s but was expected to fail.",
tt.name, actual)
}
}
}

func shuffleRecords(records []Record) []Record {
rand := rand.New(rand.NewSource(42))
newRecords := make([]Record, len(records))
for i, idx := range rand.Perm(len(records)) {
newRecords[i] = records[idx]
}
return newRecords
}

// Binary tree
func makeTwoTreeRecords() []Record {
records := make([]Record, 1<<16)
for i := range records {
if i == 0 {
records[i] = Record{ID: 0}
} else {
records[i] = Record{ID: i, Parent: i >> 1}
}
}
return shuffleRecords(records)
}

var twoTreeRecords = makeTwoTreeRecords()

func BenchmarkTwoTree(b *testing.B) {
for i := 0; i < b.N; i++ {
Build(twoTreeRecords)
}
}

// Each node but the root node and leaf nodes has ten children.
func makeTenTreeRecords() []Record {
records := make([]Record, 10000)
for i := range records {
if i == 0 {
records[i] = Record{ID: 0}
} else {
records[i] = Record{ID: i, Parent: i / 10}
}
}
return shuffleRecords(records)
}

var tenTreeRecords = makeTenTreeRecords()

func BenchmarkTenTree(b *testing.B) {
for i := 0; i < b.N; i++ {
Build(tenTreeRecords)
}
}

func makeShallowRecords() []Record {
records := make([]Record, 10000)
for i := range records {
records[i] = Record{ID: i, Parent: 0}
}
return shuffleRecords(records)
}

var shallowRecords = makeShallowRecords()

func BenchmarkShallowTree(b *testing.B) {
for i := 0; i < b.N; i++ {
Build(shallowRecords)
}
}``````
``````package tree

import (
"errors"
"sort"
)

// Record represents a post and its parent post.
type Record struct {
ID, Parent int
}

// Node represents a post in a post tree.
type Node struct {
ID       int
Children []*Node
}

// Build converts a slice of Record into a tree of posts (returning the root node).
// ->  time: O(Nlog N): sort  + (record loop * hashmap lookup in index)
// -> space: O(N), due to index
func Build(records []Record) (*Node, error) {
if len(records) < 1 {
return nil, nil
}

// sort by records, ordered by parent id ascending, record id ascending
sort.Slice(records, func(i, j int) bool {
switch {
default:
return false
case records[i].Parent < records[j].Parent:
return true
case records[i].Parent == records[j].Parent && records[i].ID < records[j].ID:
return true
}
})

if err := convertibleToTree(records); err != nil {
return nil, err
}

index := make(map[int]*Node, len(records))
// after sort, 1st record is must be root
var root *Node = &Node{ID: 0}
index[0] = root
for i := 1; i < len(records); i++ {
r := records[i]
node := Node{ID: r.ID}
index[r.ID] = &node
parent := index[r.Parent] // must exist after sort
parent.Children = append(parent.Children, &node)
}

return root, nil
}

// convertibleToTree checks whether a slice of Record satisfies constraints to create a tree.
func convertibleToTree(rs []Record) error {
// valid rs must have:
// - only one node where r.ID == r.Parent == 0
// - no of unique ID == len(rs)
// - for all non-root node, Parent < ID && 0 < ID < len(rs)

seenIDs := make(map[int]struct{}, len(rs))
// processed := 0
for _, r := range rs {
isRoot := r.ID == 0 && r.Parent == 0
validID := 0 < r.ID && r.ID < len(rs)
validParentID := r.Parent < r.ID
if !isRoot && !(validID && validParentID) {
return errors.New("record ID is invalid")
}

// processed++
// fmt.Printf("record= %#v; seen= %d; processed= %d\n", r, r.ID, processed)
seenIDs[r.ID] = struct{}{}
}
if _, seenRoot := seenIDs[0]; !seenRoot {
return errors.New("no root record")
}

// fmt.Printf("unique seen=%d; processed= %d\n", len(seenIDs), processed)
if len(seenIDs) != len(rs) {
return errors.New("not enough unique records")
}

return nil
}``````