You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut the tree at node n, the two trees would be identical.

CareerCup4.8.cpp

#include <iostream>

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

bool IsSubTree(Node*,Node*);
bool IsIdentical(Node*,Node*);
int main()
{
	Node* subroot = new Node(3);
	subroot->left = new Node(6);
	subroot->right = new Node(7);
	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<<(IsSubTree(subroot,root)?"Is ":"Is not ")<<"SubTree"<<std::endl;
	return 0;
}

bool IsSubTree(Node* T1, Node* T2)
{
	if(T2==NULL)
	{
		return false;
	}
	if(T1->data!=T2->data)
	{
		return IsSubTree(T1,T2->left)||IsSubTree(T1,T2->right);
	}
	else
	{
		if(IsIdentical(T1,T2))
		{
			return true;
		}
		else
		{
			return IsSubTree(T1,T2->left)||IsSubTree(T1,T2->right);
		}
	}
}

bool IsIdentical(Node* T1, Node* T2)
{
	if(T1->data!=T2->data)
	{
		return false;
	}
	else
	{
		if(T1->left==NULL&&T2->left==NULL&&T1->right==NULL&&T2->right==NULL)
		{
			return true;
		}
		bool flag1=true;
		bool flag2=true;
		if(((T1->left==NULL)&&(T2->left!=NULL))||((T1->left!=NULL)&&(T2->left==NULL)))
		{
			return false;
		}
		if(((T1->right==NULL)&&(T2->right!=NULL))||((T1->right!=NULL)&&(T2->right==NULL)))
		{
			return false;
		}
		if(T1->left!=NULL)
		{
			flag1=IsIdentical(T1->left,T2->left);
		}
		if(T1->right!=NULL)
		{
			flag2=IsIdentical(T1->right,T2->right);
		}
		return flag1&&flag2;
	}
}