First Common Ancestor

CrackingTheCodeInterview4.8.cpp

#include <iostream>
#include <string>
#include <vector>
#include <list>

using namespace std;

template <class T> class Node {

public:
	/* Members */
	T val;
	vector<Node<T>*> child;

	// constructor
	Node(T val) {
		this->val = val;
	}

	virtual ~Node() {
		for (typename vector<Node<T>*>::iterator it=child.begin() ; it != child.end() ; it++) {
			delete *it;
		}
	}

	void addChild(Node<T>* n) {
		child.push_back(n);
	}

	list<Node*>* getShortestPath(Node* n) {
		if (n == nullptr)
			return nullptr;

		if (n == this)
			return new list<Node*>(1,n);

		for (int i=0 ; i < child.size() ; i++) {
			list<Node*>* path = child[i]->getShortestPath(n);
			if (path != nullptr) {
				path->push_front(this);
				return path;
			}
		}

		return nullptr;
	}

	Node<T>* firstAnc(Node* a, Node* b) {
		list<Node*>* aPath = getShortestPath(a);
		list<Node*>* bPath = getShortestPath(b);

		Node<T>* anc;
		typename list<Node<T>* >::iterator aIt;
		typename list<Node<T>* >::iterator bIt;

		for (aIt=aPath->begin(), bIt=bPath->begin() ; aIt != aPath->end() && bIt != bPath->end() && *aIt == *bIt ; aIt++, bIt++ ) {
			anc = *aIt;
		}

		delete aPath;
		delete bPath;

		return anc;
	}
};

int main() {
	Node<string>* a = new Node<string>("A");
	Node<string>* b = new Node<string>("B");
	Node<string>* c = new Node<string>("C");
	Node<string>* d = new Node<string>("D");
	Node<string>* e = new Node<string>("E");
	a->addChild(b);
	a->addChild(c);
	c->addChild(d);
	c->addChild(e);

	cout << (a->firstAnc(b,c))->val << endl;

	delete a;
}