Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 48
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given pre-order and in-order traversals of a binary tree, write a function to reconstruct the tree.

For example, given the following preorder traversal:

```[a, b, d, e, c, f, g]```

And the following inorder traversal:

```[d, b, e, a, f, c, g]```

You should return the following tree:
```
    a
   / \
  b   c
 / \ / \
d  e f  g
```

Pull request:
Day48
Resolves #109 .

Patch:
diff --git a/README.md b/README.md
index bc3c968..368669d 100644
--- a/README.md
+++ b/README.md
@@ -60,6 +60,7 @@ problems from
 * [Day 45](https://github.com/vaskoz/dailycodingproblem-go/issues/101)
 * [Day 46](https://github.com/vaskoz/dailycodingproblem-go/issues/103)
 * [Day 47](https://github.com/vaskoz/dailycodingproblem-go/issues/105)
+* [Day 48](https://github.com/vaskoz/dailycodingproblem-go/issues/109)
 * [Day 49](https://github.com/vaskoz/dailycodingproblem-go/issues/107)
 * [Day 50](https://github.com/vaskoz/dailycodingproblem-go/issues/110)
 * [Day 52](https://github.com/vaskoz/dailycodingproblem-go/issues/113)
diff --git a/day48/problem.go b/day48/problem.go
new file mode 100644
index 0000000..76f9546
--- /dev/null
+++ b/day48/problem.go
@@ -0,0 +1,32 @@
+package day48
+
+// BinaryTree is a binary tree with rune values.
+type BinaryTree struct {
+	value       string
+	left, right *BinaryTree
+}
+
+// Reconstruct takes a pre-order and in-order string representation
+// and then returns a BinaryTree that conforms to both of those representations.
+func Reconstruct(preorder, inorder []string) (*BinaryTree, []string) {
+	node := &BinaryTree{preorder[0], nil, nil}
+	preorder = preorder[1:]
+	if len(inorder) == 1 {
+		return node, preorder
+	}
+	index := search(inorder, node.value)
+	node.left, preorder = Reconstruct(preorder, inorder[:index])
+	node.right, preorder = Reconstruct(preorder, inorder[index+1:])
+	return node, preorder
+}
+
+func search(strs []string, target string) int {
+	var result int
+	for index, str := range strs {
+		if str == target {
+			result = index
+			break
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day48/problem_test.go b/day48/problem_test.go
new file mode 100644
index 0000000..858749b
--- /dev/null
+++ b/day48/problem_test.go
@@ -0,0 +1,50 @@
+package day48
+
+import (
+	"testing"
+)
+
+var testcases = []struct {
+	preorder, inorder []string
+	expected          *BinaryTree
+}{
+	{[]string{"a", "b", "d", "e", "c", "f", "g"},
+		[]string{"d", "b", "e", "a", "f", "c", "g"},
+		&BinaryTree{"a",
+			&BinaryTree{"b", &BinaryTree{"d", nil, nil}, &BinaryTree{"e", nil, nil}},
+			&BinaryTree{"c", &BinaryTree{"f", nil, nil}, &BinaryTree{"g", nil, nil}}}},
+}
+
+func TestReconstructBinaryTree(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, _ := Reconstruct(tc.preorder, tc.inorder); !treesEqual(result, tc.expected) {
+			t.Errorf("Expected both trees to be equal")
+		}
+	}
+}
+
+func BenchmarkReconstructBinaryTree(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Reconstruct(tc.preorder, tc.inorder)
+		}
+	}
+}
+
+func treesEqual(a, b *BinaryTree) bool {
+	if a == nil && b == nil {
+		return true
+	} else if (a == nil && b != nil) || (a != nil && b == nil) {
+		return false
+	}
+	if a.value != b.value {
+		return false
+	}
+	if leftEqual := treesEqual(a.left, b.left); !leftEqual {
+		return false
+	} else if rightEqual := treesEqual(a.right, b.right); !rightEqual {
+		return false
+	}
+	return true
+}
diff --git a/day52/problem_test.go b/day52/problem_test.go
index 592d3e4..afa28fd 100644
--- a/day52/problem_test.go
+++ b/day52/problem_test.go
@@ -3,6 +3,7 @@ package day52
 import "testing"
 
 func TestLRUCache(t *testing.T) {
+	t.Parallel()
 	lru := NewLRU(3)
 	for i := 0; i < 6; i++ {
 		lru.Set(i, i+1)