Skip to content

Instantly share code, notes, and snippets.

@P-A-R-U-S
Last active May 31, 2020 21:46
Show Gist options
  • Save P-A-R-U-S/6f3440de0702582841f5cc80c78f121d to your computer and use it in GitHub Desktop.
Save P-A-R-U-S/6f3440de0702582841f5cc80c78f121d to your computer and use it in GitHub Desktop.
Cracking the Coding Interview - Task - 4.8
/*
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)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment