Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 258
Good morning! Here's your coding interview problem for today.

This problem was asked by Morgan Stanley.

In Ancient Greece, it was common to write text with the first line going left to right, the second line going right to left, and continuing to go back and forth. This style was called "boustrophedon".

Given a binary tree, write an algorithm to print the nodes in boustrophedon order.

For example, given the following tree:
```
       1
    /     \
  2         3
 / \       / \
4   5     6   7
```
You should return `[1, 3, 2, 4, 5, 6, 7]`.

Pull request description:
Day258
Resolves #530.

Patch:
diff --git a/README.md b/README.md
index 7a8bb45..7c52ce5 100644
--- a/README.md
+++ b/README.md
@@ -267,3 +267,4 @@ problems from
 * [Day 253](https://github.com/vaskoz/dailycodingproblem-go/issues/521)
 * [Day 254](https://github.com/vaskoz/dailycodingproblem-go/issues/523)
 * [Day 255](https://github.com/vaskoz/dailycodingproblem-go/issues/525)
+* [Day 258](https://github.com/vaskoz/dailycodingproblem-go/issues/530)
diff --git a/day258/problem.go b/day258/problem.go
new file mode 100644
index 0000000..baafe42
--- /dev/null
+++ b/day258/problem.go
@@ -0,0 +1,39 @@
+package day258
+
+// IntBinaryTree is a binary tree of integers.
+type IntBinaryTree struct {
+	Value       int
+	Left, Right *IntBinaryTree
+}
+
+// BoustrophedonOrder works as follows.
+// https://en.wikipedia.org/wiki/Boustrophedon
+func BoustrophedonOrder(root *IntBinaryTree) []int {
+	if root == nil {
+		return nil
+	}
+	var result []int
+	levels := []*IntBinaryTree{root}
+	leftToRight := true
+	for len(levels) != 0 {
+		var nextLevel []*IntBinaryTree
+		for _, n := range levels {
+			result = append(result, n.Value)
+			if n.Left != nil {
+				nextLevel = append(nextLevel, n.Left)
+			}
+			if n.Right != nil {
+				nextLevel = append(nextLevel, n.Right)
+			}
+		}
+		if !leftToRight {
+			toReverse := result[len(result)-len(levels):]
+			for i := 0; i < len(toReverse)/2; i++ {
+				toReverse[i], toReverse[len(toReverse)-1-i] = toReverse[len(toReverse)-1-i], toReverse[i]
+			}
+		}
+		leftToRight = !leftToRight
+		levels = nextLevel
+	}
+	return result
+}


Test patch:
diff --git a/day258/problem_test.go b/day258/problem_test.go
new file mode 100644
index 0000000..490e576
--- /dev/null
+++ b/day258/problem_test.go
@@ -0,0 +1,47 @@
+package day258
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	root     *IntBinaryTree
+	expected []int
+}{
+	{nil, nil},
+	{
+		&IntBinaryTree{
+			1,
+			&IntBinaryTree{
+				2,
+				&IntBinaryTree{4, nil, nil},
+				&IntBinaryTree{5, nil, nil},
+			},
+			&IntBinaryTree{
+				3,
+				&IntBinaryTree{6, nil, nil},
+				&IntBinaryTree{7, nil, nil},
+			},
+		},
+		[]int{1, 3, 2, 4, 5, 6, 7},
+	},
+}
+
+func TestBoustrophedonOrder(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := BoustrophedonOrder(tc.root); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkBoustrophedonOrder(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BoustrophedonOrder(tc.root)
+		}
+	}
+}