Cracking the Coding Interview - Task - 4.8

Cracking_the_Coding_Interview_4-8_test.go

/*
First Common Ancestor: Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. 
Avoid storing additional nodes in a data structure. 
NOTE: This is not necessarily a binary search tree.
Hints: # 10, #16, #28, #36, #46, #70, #80, #96
*/

/*
Создайте алгоритм и напишите код поиска первого общего предка двух узлов бинарного дерева. Постарайтесь избежать
хранения дополнительных узлов в структуре данных.

Примечание: бинарное дерево не обязательно является бинарным деревом поиска.

Подсказки: 10,16,28,36,46, 70,80,96
*/

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

func find_Common_Ancestor(root *Node, a value, b value) *value {
	if root == nil {
		return nil
	}
	if root.id == a || root.id == b{
		return &root.id
	}
	l_path := find_Common_Ancestor_2(root.left,a,b)
	r_path := find_Common_Ancestor_2(root.right,a,b)

	if l_path != nil && r_path != nil {
		return &root.id
	}
	if l_path != nil {
		return l_path
	}
	if r_path != nil {
		return r_path
	}

	return nil
}


func Test_Find_Common_Ancestor(t *testing.T) {
	testDatas := []struct{
		root *Node
		a value
		b value
		result value
	} {
		{
			&Node{
				id:    1,
				left:  &Node{
					id:    2,
					left:  &Node{
						id:    4,
					},
					right: &Node{
						id:    5,
					},
				},
				right: &Node{
					id:    3,
					left:  &Node{
						id:    6,
						right:&Node{
							id:    8,
							left:&Node{
								id:    13,
								left:&Node{
									id:    15,
									right:&Node{
										id:    16,
										right:&Node{
											id:    17,
										},
									},
								},
								right:&Node{
									id:    14,
								},
							},
						},
					},
					right: &Node{
						id:    7,
						right:&Node{
							id:    9,
							left:&Node{
								id:    10,
							},
							right:&Node{
								id:    11,
								right:&Node{
									id:    12,
								},
							},
						},
					},
				},
			},
			17,
			14,
			13,
		},
		{
			&Node{
				id:    1,
				left:  &Node{
					id:    2,
					left:  &Node{
						id:    4,
					},
					right: &Node{
						id:    5,
					},
				},
				right: &Node{
					id:    3,
					left:  &Node{
						id:    6,
						right:&Node{
							id:    8,
							left:&Node{
								id:    13,
								left:&Node{
									id:    15,
									right:&Node{
										id:    16,
										right:&Node{
											id:    17,
										},
									},
								},
								right:&Node{
									id:    14,
								},
							},
						},
					},
					right: &Node{
						id:    7,
						right:&Node{
							id:    9,
							left:&Node{
								id:    10,
							},
							right:&Node{
								id:    11,
								right:&Node{
									id:    12,
								},
							},
						},
					},
				},
			},
			8,
			11,
			3,
		},
		{
			&Node{
				id:    1,
				left:  &Node{
					id:    2,
					left:  &Node{
						id:    4,
					},
					right: &Node{
						id:    5,
					},
				},
				right: &Node{
					id:    3,
					left:  &Node{
						id:    6,
						right:&Node{
							id:    8,
							left:&Node{
								id:    13,
								left:&Node{
									id:    15,
									right:&Node{
										id:    16,
										right:&Node{
											id:    17,
										},
									},
								},
								right:&Node{
									id:    14,
								},
							},
						},
					},
					right: &Node{
						id:    7,
						right:&Node{
							id:    9,
							left:&Node{
								id:    10,
							},
							right:&Node{
								id:    11,
								right:&Node{
									id:    12,
								},
							},
						},
					},
				},
			},
			4,
			13,
			1,
		},
	}

	for _, td := range testDatas {
		r := *find_Common_Ancestor(td.root,td.a, td.b)
		if r != td.result {
			t.Errorf("Source: %v \n Expected: %v, Actual: %v",
				td.root,
				td.result,
				r)
		}
	}
}