Youngest Common Ancestor

• Time : O(d)
• Space : O(1)

c++

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;
}