Cracking the Coding Interview - Task - 4.9

Cracking_the_Coding_Interview_4-9_test.go

package Part_4

import (
	"fmt"
	"testing"
)

/*
BST Sequences: A binary search tree was created by traversing through an array from left to right and inserting each element.
Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.
*/

/* 
Бинарное дерево поиска было создано обходом массива слева направо и вставкой каждого элемента.
Для заданного бинарного дерева поиска с разными элементами выведите все возможные массивы,
которые могли привести к созданию этого дерева.
Пример: Ввод:
    2
   / \
  1   3
Вывод: 
	{2, 1, 3}, 
	{2, 3, 1}
Подсказки:39,48,66,82
*/

/*
**Problem 4.9. BST Sequences:** A binary search tree was created by traversing through an array from left to right and
inserting each element. Given a binary search tree with distinct elements,
print all possible arrays that could have led to this tree.

**Solution.**

Let's start with an example.

```
    4
   / \
  2   5
 / \   \
1   3   6
```

To construct this tree we must insert the node 4 first. This node is always going to be the first element
in each of the possible solution. Lets remove this node from the tree.

```
  2    5
 / \    \
1   3    6
```

To continue construcing the tree from the example we now have a choice of eather inserting 2 or 5.
Notice that both are the roots of the respective subtrees. Lets start with node 2 and remove it from the tree.

```
1   3   5
         \
          6
```

We are left with 3 subtrees. We now have a choice of removing either 1, 3 or 5.

You can cleary see that there is an inductive step which we can use to implement our solution:
```
start with a root of the tree (the only valid choice)

for each of the current valid choices:
- remove one of the roots (valid choices), add its children to the set of choices
- recursively find all possible solutions for the new set of choices
- append the root to the head of each of those solutions

the recursion ends when there are no remaining nodes (choices) left
```

**Implementation.**

Here's an actual code written.
It uses arrays, but it might make sense to use lists instead.
The key to implementing the algorithm is to keep the array of all choices after removing the node from the tree.


Output:

```
[4, 2, 5, 1, 3, 6]
[4, 2, 5, 1, 6, 3]
[4, 2, 5, 3, 1, 6]
[4, 2, 5, 3, 6, 1]
[4, 2, 5, 6, 1, 3]
[4, 2, 5, 6, 3, 1]
[4, 2, 1, 5, 3, 6]
[4, 2, 1, 5, 6, 3]
[4, 2, 1, 3, 5, 6]
[4, 2, 3, 5, 1, 6]
[4, 2, 3, 5, 6, 1]
[4, 2, 3, 1, 5, 6]
[4, 5, 2, 6, 1, 3]
[4, 5, 2, 6, 3, 1]
[4, 5, 2, 1, 6, 3]
[4, 5, 2, 1, 3, 6]
[4, 5, 2, 3, 6, 1]
[4, 5, 2, 3, 1, 6]
[4, 5, 6, 2, 1, 3]
[4, 5, 6, 2, 3, 1]
```


*/

type value int
type Node struct {
	id value
	left *Node
	right *Node
}


func bstSequences(roots []*Node) [][]value {
	var result [][]value

	for _, r := range roots {
		var choices []*Node
		for _, cr := range roots {
			if cr.id != r.id {
				choices = append(choices, cr)
			}
		}
		if r.left != nil {
			choices = append(choices, r.left)
		}
		if r.right != nil {
			choices = append(choices, r.right)
		}
		if len(choices) == 0 {
			result = append(result,[]value{r.id})
		}
		for _, s := range bstSequences(choices) {
			result = append(result, append([]value{r.id}, s...))
		}
	}

	return result
}

func Test_BST_Sequences(t *testing.T) {
	testDatas := []struct{
		root *Node
		result [][]value
	} {
		{
			&Node{
				id:    2,
				left:  &Node{
					id:    1,
				},
				right: &Node{
					id:    3,
				},
			},
			[][]value{ {2,1,3}, {2,3,1}},
		},
		{
			&Node{
				id:    4,
				left:  &Node{
					id:    2,
					left:  &Node{
						id:    1,
					},
					right: &Node{
						id:    3,
					},
				},
				right: &Node{
					id:    5,
					left:  &Node{
						id:    6,
					},
				},
			},
			[][]value{
				{4, 2, 5, 1, 3, 6,},
				{4, 2, 5, 1, 6, 3,},
				{4, 2, 5, 3, 1, 6,},
				{4, 2, 5, 3, 6, 1,},
				{4, 2, 5, 6, 1, 3,},
				{4, 2, 5, 6, 3, 1,},
				{4, 2, 1, 5, 3, 6,},
				{4, 2, 1, 5, 6, 3,},
				{4, 2, 1, 3, 5, 6,},
				{4, 2, 3, 5, 1, 6,},
				{4, 2, 3, 5, 6, 1,},
				{4, 2, 3, 1, 5, 6,},
				{4, 5, 2, 6, 1, 3,},
				{4, 5, 2, 6, 3, 1,},
				{4, 5, 2, 1, 6, 3,},
				{4, 5, 2, 1, 3, 6,},
				{4, 5, 2, 3, 6, 1,},
				{4, 5, 2, 3, 1, 6,},
				{4, 5, 6, 2, 1, 3,},
				{4, 5, 6, 2, 3, 1,},
			},
		},
	}

	for _, td := range testDatas {
		r := bstSequences([]*Node{td.root})
		for _, a := range r {
			fmt.Println(a)
		}

		IsArrayOfArraysEquals :=func (a [][]value, b [][]value) bool {
			if len(a) != len(b) {
				return false
			}

			var i int
			var j int

			for i < len(a) || j < len(b) {

				for index, v := range a[i] {
					if v != b[j][index] {
						return false
					}
				}
				i++
				j++
			}
			return true
		}

		if !IsArrayOfArraysEquals(r,td.result) {
			t.Errorf("Source: %v \n Expected: %v, Actual: %v",
				td.root,
				td.result,
				r)
		}
	}
}