[AlgoExpert] Youngest Common Ancestor

Youngest Common Ancestor

  • Time : O(d)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class AncestralTree {
public:
char name;
AncestralTree *ancestor;

AncestralTree(char name) {
this->name = name;
this->ancestor = nullptr;
}

void addAsAncestor(vector<AncestralTree *> descendants);
};

AncestralTree *getYoungestCommonAncestor(AncestralTree *topAncestor,
AncestralTree *descendantOne,
AncestralTree *descendantTwo) {
int lvl1 = 0, lvl2 = 0;
AncestralTree *tmp = descendantOne;
while(tmp != topAncestor) {
lvl1++;
tmp = tmp->ancestor;
}
tmp = descendantTwo;
while(tmp != topAncestor) {
lvl2++;
tmp = tmp->ancestor;
}
while(lvl1 != lvl2) {
if(lvl1 > lvl2) {
descendantOne = descendantOne->ancestor;
lvl1--;
} else {
descendantTwo = descendantTwo->ancestor;
lvl2--;
}
}
while(descendantOne != descendantTwo) {
descendantOne = descendantOne->ancestor;
descendantTwo = descendantTwo->ancestor;
}
return descendantOne;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/16/PS/AlgoExpert/youngest-common-ancesstor/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.