Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 215
Good morning! Here's your coding interview problem for today.

This problem was asked by Yelp.

The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out.

More rigorously, we can define it as follows:

The horizontal distance of the root is 0.
The horizontal distance of a left child is hd(parent) - 1.
The horizontal distance of a right child is hd(parent) + 1.
For example, for the following tree, hd(1) = -2, and hd(6) = 0.
```
             5
          /     \
        3         7
      /  \      /   \
    1     4    6     9
   /                /
  0                8
```
The bottom view of a tree, then, consists of the lowest node at each horizontal distance. If there are two nodes at the same depth and horizontal distance, either is acceptable.

For this tree, for example, the bottom view could be `[0, 1, 3, 6, 8, 9]`.

Given the root to a binary tree, return its bottom view.

Pull request:
Day215
Resolves #443.

Patch:
diff --git a/README.md b/README.md
index e2c6bd5..7a38b7b 100644
--- a/README.md
+++ b/README.md
@@ -225,3 +225,4 @@ problems from
 * [Day 212](https://github.com/vaskoz/dailycodingproblem-go/issues/436)
 * [Day 213](https://github.com/vaskoz/dailycodingproblem-go/issues/439)
 * [Day 214](https://github.com/vaskoz/dailycodingproblem-go/issues/441)
+* [Day 215](https://github.com/vaskoz/dailycodingproblem-go/issues/443)
diff --git a/day215/problem.go b/day215/problem.go
new file mode 100644
index 0000000..8cbb82a
--- /dev/null
+++ b/day215/problem.go
@@ -0,0 +1,48 @@
+package day215
+
+import (
+	"sort"
+)
+
+// BinaryTree is a binary tree that can hold any value.
+type BinaryTree struct {
+	Value       interface{}
+	Left, Right *BinaryTree
+}
+
+type value struct {
+	height int
+	value  interface{}
+}
+
+// BottomView returns the bottom-view of the binary
+// tree.
+func BottomView(root *BinaryTree) []interface{} {
+	pos := make(map[int]value)
+	bottomView(root, 0, 0, pos)
+	result := make([]interface{}, len(pos))
+	keys := make([]int, 0, len(pos))
+	for k := range pos {
+		keys = append(keys, k)
+	}
+	sort.Ints(keys)
+	for i, key := range keys {
+		result[i] = pos[key].value
+	}
+	return result
+}
+
+func bottomView(node *BinaryTree, dist, height int, pos map[int]value) {
+	if node == nil {
+		return
+	}
+	if val, found := pos[dist]; found {
+		if height >= val.height {
+			pos[dist] = value{height, node.Value}
+		}
+	} else {
+		pos[dist] = value{height, node.Value}
+	}
+	bottomView(node.Left, dist-1, height+1, pos)
+	bottomView(node.Right, dist+1, height+1, pos)
+}


Test patch:
diff --git a/day215/problem_test.go b/day215/problem_test.go
new file mode 100644
index 0000000..781cdd1
--- /dev/null
+++ b/day215/problem_test.go
@@ -0,0 +1,52 @@
+package day215
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	tree     *BinaryTree
+	expected []interface{}
+}{
+	{&BinaryTree{
+		5,
+		&BinaryTree{
+			3,
+			&BinaryTree{
+				1,
+				&BinaryTree{0, nil, nil},
+				nil,
+			},
+			&BinaryTree{4, nil, nil},
+		},
+		&BinaryTree{
+			7,
+			&BinaryTree{6, nil, nil},
+			&BinaryTree{
+				9,
+				&BinaryTree{8, nil, nil},
+				nil,
+			},
+		},
+	},
+		[]interface{}{0, 1, 3, 6, 8, 9},
+	},
+}
+
+func TestBottomView(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := BottomView(tc.tree); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkBottomView(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BottomView(tc.tree)
+		}
+	}
+}