Avatar of exklamationmark

exklamationmark's solution

to Tree Building in the Go Track

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

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
	// !root -> add to index && add to parent's children
	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
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?