Cracking the Coding Interview - Task - 4.12 - Find path equal K in binary tree

Cracking_the_Coding_Interview_4-12_test.go

package Part_4

import (
	"testing"
)

/*

Paths with Sum: You are given a binary tree in which each node contains an integer value (which might be positive or negative).
Design an algorithm to count the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
Hints: #6, #74, #52, #68, #77, #87, #94, #703, #708, #115
*/


/*
Дано бинарное дерево, в котором каждый узел содержит целое число (по­ложительное или отрицательное).
Разработайте алгоритм для подсчета всех путей, сумма значений которых соответствует заданной величине.
Обратите внимание, что путь не обязан начинаться или заканчиваться в корневом или листовом узле,
но он должен идти вниз (переходя только от родительских узлов к дочерним).

Подсказки: 6, 14,52,68, 77,87,94, 103, 108, 115
*/

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

func findSumInBinaryTree(root *Node, sum int, path *[]int, result *[][]int) {
	if root == nil {
		return
	}

	*path = append(*path, root.id)
	findSumInBinaryTree(root.left, sum, path, result)
	findSumInBinaryTree(root.right, sum, path, result)

	s := 0
	for i:=len(*path)-1; i >=0; i--{
		s += (*path)[i]
		if s == sum {
			a := make([]int,len(*path) - i)
			copy(a,(*path)[i:])
			*result = append(*result, a)
		}
	}
	*path = (*path)[:len(*path)-1]
}

func Test_Find_Sum_In_BinaryTree(t *testing.T) {
	testDatas := []struct{
		root *Node
		sum int
		result [][]int
		count int
	} {
		{
			&Node{
				id:    5,
				left:  &Node{
					id:    2,
					left:  &Node{
						id:    1,
						left:  nil,
						right: &Node{
							id:    3,
							left:  &Node{
								id:    4,
								left:  nil,
								right: nil,
							},
							right: &Node{
								id:    1,
								left:  &Node{
									id:    1,
									left:  nil,
									right: nil,
								},
								right: nil,
							},
						},
					},
					right: nil,
				},
				right: &Node{
					id:    10,
					left:  &Node{
						id:    -3,
						left:  nil,
						right: &Node{
							id:    2,
							left:  nil,
							right: &Node{
								id:    0,
								left:  &Node{
									id:    0,
									left:  &Node{
										id:    1,
										left:  nil,
										right: nil,
									},
									right: nil,
								},
								right: &Node{
									id:    1,
									left:  &Node{
										id:    3,
										left:  nil,
										right: nil,
									},
									right: &Node{
										id:    4,
										left:  &Node{
											id:    7,
											left:  nil,
											right: &Node{
												id:    3,
												left:  nil,
												right: nil,
											},
										},
										right: nil,
									},
								},
							},
						},
					},
					right: &Node{
						id:    -4,
						left:  nil,
						right: &Node{
							id:    -6,
							left:  nil,
							right: nil,
						},
					},
				},
			},
			15,
			[][]int{
				{5,2,1,3,4},
				{5,10,-3,2,0,0,1},
				{1,4,7,3},
				{0,1,4,7,3},
				{5,10,-3,2,0,1},
				{5,10},
			},
			6,
		},
	}

	IsIntsOfIntsArraysEquals := func (a [][]int, b [][]int) 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
	}

	for _, td := range testDatas {
		var r [][]int
		findSumInBinaryTree(td.root,td.sum,&[]int{}, &r)

		if len(r) != td.count {
			t.Errorf("Source: Count %v \nSum:%d\n Exepected: %d\n Actual: %d",
				td.root,
				td.sum,
				td.count,
				len(r))
		}

		if !IsIntsOfIntsArraysEquals(r, td.result) {
			t.Errorf("Source: Arrays %v \nSum:%d\n Exepected: %d\n Actual: %d",
				td.root,
				td.sum,
				td.result,
				r)
		}


	}
}