CC150 4.8

4_8.cpp

/* CC150 4.8
 * 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 Tl.
 * A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2.
 * That is, if you cut off the tree at node n, the two trees would be identical.
 */

#include "bstree.h" // https://gist.github.com/df2d3552fbe8c2342541
#include <sstream>

using namespace std;

bool treeMatch(Node *t1, Node *t2)
{
	if (t1 == nullptr && t2 == nullptr) // both trees are empty
		return true;
	if (t1 == nullptr || t2 == nullptr) // one of the two trees is empty
		return false;
	return t1->data == t2->data // both trees are non-empty, first compare current node then compare subtrees
		&& treeMatch(t1->left, t2->left) && treeMatch(t1->right, t2->right);
}

bool isSubtree(Node *t1, Node *t2)
{
	if (t2 == nullptr) // tree t2 is empty
		return true;
	if (t1 == nullptr) // tree t1 is empty while t2 is not
		return false;
	if (t1->data == t2->data) { // both trees are non-empty
		if (treeMatch(t1, t2))
			return true; // find exact match
	}
	return isSubtree(t1->left, t2) || isSubtree(t1->right, t2); // traverse t1 and keep searching for t2
}

int main()
{
	bstree t1; // tree t1
	string key1; getline(cin, key1); // data for tree t1
	istringstream din(key1);
	int key;
	while (din >> key)
		t1.insert(key);
	bstree t2; // tree t2
	string key2; getline(cin, key2); // data for tree t2
	din.clear(); din.str(key2);
	while (din >> key)
		t2.insert(key);
	if (isSubtree(t1.getRoot(), t2.getRoot()))
		cout << "T2 is subtree of T1!" << endl;
	else
		cout << "T2 is not subtree of T1!" << endl;
	return 0;
}