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.

careercup4.7.cpp

#include <iostream>

struct Node
{
  int data;
	Node* left;
	Node* right;
	Node()
	{
		left = NULL;
		right = NULL;
	}
	Node(int value)
	{
		data = value;
		left = NULL;
		right = NULL;
	}
};

Node* GetParent(Node*, Node*, Node*);
bool HasNode(Node*,Node*);
int _tmain(int argc, _TCHAR* argv[])
{
	Node* root = new Node(1);
	root->left = new Node(2);
	root->right = new Node(3);
	root->left->left = new Node(4);
	root->left->right = new Node(5);
	root->right->left = new Node(6);
	root->right->right = new Node(7);

	std::cout<<((GetParent(root,root->right->left,root->right->right))->data)<<std::endl;
	return 0;
}

Node* GetParent(Node* root, Node* node1, Node* node2)
{
	if(HasNode(root->left,node1)&&HasNode(root->left,node2))
	{
		return GetParent(root->left,node1,node2);
	}
	if(HasNode(root->right,node1)&&HasNode(root->right,node2))
	{
		return GetParent(root->right,node1,node2);
	}
	else
	{
		return root;
	}
}

bool HasNode(Node* root,Node* aim)
{
	if(root == aim)
	{
		return true;
	}
	else if(root->left==NULL&&root->right==NULL)
	{
		return false;
	}
	else
	{
		bool flagleft = false;
		bool flagright = false;
		if(root->left!=NULL)
		{
			flagleft = HasNode(root->left, aim);
		}
		if(root->right!=NULL)
		{
			flagright = HasNode(root->right,aim);
		}
		return flagleft||flagright;
	}
}