Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 223
Good morning! Here's your coding interview problem for today.

This problem was asked by Palantir.

Typically, an implementation of in-order traversal of a binary tree has O(h) space complexity, where h is the height of the tree. Write a program to compute the in-order traversal of a binary tree using O(1) space.

Pull request description:
Day223
Resolves #460.

Patch:
diff --git a/README.md b/README.md
index 33dcb98..5a4dc8b 100644
--- a/README.md
+++ b/README.md
@@ -233,3 +233,4 @@ problems from
 * [Day 220](https://github.com/vaskoz/dailycodingproblem-go/issues/453)
 * [Day 221](https://github.com/vaskoz/dailycodingproblem-go/issues/454)
 * [Day 222](https://github.com/vaskoz/dailycodingproblem-go/issues/458)
+* [Day 223](https://github.com/vaskoz/dailycodingproblem-go/issues/460)
diff --git a/day223/problem.go b/day223/problem.go
new file mode 100644
index 0000000..e7e88fa
--- /dev/null
+++ b/day223/problem.go
@@ -0,0 +1,34 @@
+package day223
+
+// BinaryTree is a simple binary tree.
+type BinaryTree struct {
+	Value       interface{}
+	Left, Right *BinaryTree
+}
+
+// InorderMorrisTraversal performs a Morris Inorder traversal.
+// Uses O(1) extra space.
+func InorderMorrisTraversal(root *BinaryTree) []interface{} {
+	var inorder []interface{}
+	curr := root
+	for curr != nil {
+		if curr.Left == nil {
+			inorder = append(inorder, curr.Value)
+			curr = curr.Right
+		} else {
+			pre := curr.Left
+			for pre.Right != nil && pre.Right != curr {
+				pre = pre.Right
+			}
+			if pre.Right == nil {
+				pre.Right = curr
+				curr = curr.Left
+			} else {
+				pre.Right = nil
+				inorder = append(inorder, curr.Value)
+				curr = curr.Right
+			}
+		}
+	}
+	return inorder
+}


Test patch:
diff --git a/day223/problem_test.go b/day223/problem_test.go
new file mode 100644
index 0000000..491d4dc
--- /dev/null
+++ b/day223/problem_test.go
@@ -0,0 +1,39 @@
+package day223
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	root    *BinaryTree
+	inorder []interface{}
+}{
+	{&BinaryTree{
+		1,
+		&BinaryTree{
+			2,
+			&BinaryTree{4, nil, nil},
+			&BinaryTree{5, nil, nil},
+		},
+		&BinaryTree{3, nil, nil},
+	},
+		[]interface{}{4, 2, 5, 1, 3},
+	},
+}
+
+func TestInorderMorrisTraversal(t *testing.T) {
+	for _, tc := range testcases {
+		if result := InorderMorrisTraversal(tc.root); !reflect.DeepEqual(tc.inorder, result) {
+			t.Errorf("Expected %v, got %v", tc.inorder, result)
+		}
+	}
+}
+
+func BenchmarkInorderMorrisTraversal(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			InorderMorrisTraversal(tc.root)
+		}
+	}
+}