Test if sub-tree
Test if a binary tree (tree2) is a sub-tree of another larger binary tree (tree1).
/*
* CheckIfSubTree.cpp
*
* Created on: Apr 21, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
class BinaryTreeNode {
public :
BinaryTreeNode(int d) : left(NULL), right(NULL), data(d) {}
~BinaryTreeNode() {
if (left != NULL) {
delete left;
left = NULL;
}
if (right != NULL) {
delete right;
right = NULL;
}
}
BinaryTreeNode *left;
BinaryTreeNode *right;
int data;
};
/**
* Create a Binary Tree from any array. The tree is created such that beginning
* of the array is mapped to the root of the tree and subsequent array elements
* are added as the children, going from left to right and top to bottom
*/
BinaryTreeNode *createBinaryTreeFromArray(int *array, int size) {
if (array == NULL) {
return NULL;
}
queue<BinaryTreeNode *> myQueue;
BinaryTreeNode *root = new BinaryTreeNode(array[0]);
myQueue.push(root);
bool done = false;
int i = 1;
while (!done) {
BinaryTreeNode *node = myQueue.front();
if (node->left == NULL) {
node->left = new BinaryTreeNode(array[i]);
myQueue.push(node->left);
i++;
}
else if (node->right == NULL) {
node->right = new BinaryTreeNode(array[i]);
myQueue.push(node->right);
i++;
}
else {
myQueue.pop();
}
if (i == size)
done = true;
}
return root;
}
void printTree(BinaryTreeNode *root) {
if (root == NULL){
return;
}
queue<BinaryTreeNode *> treeQueue;
queue<int> levelQueue;
queue<int> parentQueue;
queue<string> rightLeftFlagQueue;
treeQueue.push(root);
levelQueue.push(0);
parentQueue.push(root->data);
rightLeftFlagQueue.push("Top");
cout << "Level 1: ";
int prevLevel = 0;
while(! treeQueue.empty()) {
BinaryTreeNode *node = treeQueue.front();
int level = levelQueue.front();
if (node != NULL) {
if (level > prevLevel) {
prevLevel = level;
cout << endl;
cout << "Level " << level + 1 << ": ";
}
int parentData = parentQueue.front();
string rightLeftFlag = rightLeftFlagQueue.front();
if (level > 0) {
cout << parentData << "-->" ;
}
cout << node->data << " ";
if (level > 0) {
cout << rightLeftFlag << " ";
}
if (node->left != NULL) {
treeQueue.push(node->left);
levelQueue.push(level + 1);
parentQueue.push(node->data);
rightLeftFlagQueue.push("L");
}
if (node->right != NULL) {
treeQueue.push(node->right);
levelQueue.push(level + 1);
parentQueue.push(node->data);
rightLeftFlagQueue.push("R");
}
}
treeQueue.pop();
levelQueue.pop();
parentQueue.pop();
rightLeftFlagQueue.pop();
}
}
bool areTreesSame(BinaryTreeNode *tree1, BinaryTreeNode *tree2) {
if ((tree1 == NULL) && (tree2 == NULL))
return true;
if (tree1 == NULL)
return false;
if (tree1->data != tree2->data)
return false;
return (areTreesSame(tree1->left, tree2->left) &&
areTreesSame(tree1->right, tree2->right));
}
bool doesTree1ContainTree2(BinaryTreeNode *tree1, BinaryTreeNode *tree2) {
if (tree1 == NULL)
return false;
if (tree1->data == tree2->data) {
if (areTreesSame(tree1, tree2))
return true;
}
else {
return (doesTree1ContainTree2(tree1->left, tree2) ||
doesTree1ContainTree2(tree1->right, tree2));
}
return false;
}
/**
* Test the code
*/
int main() {
int treeArray[] = { 9, 13, 14, 15, 16, 17, 1, 2, 10, 11, 12, 3, 4, 5, 6, 7,
8, 20, 22, 21, 18, 19, 25, 24, 23};
cout << "Array 1: " << endl;
for (int i=0; i<25; i++) {
cout << treeArray[i] << " ";
}
//Binary tree created from array with each element
BinaryTreeNode *tree1 = createBinaryTreeFromArray(treeArray, 25);
cout << endl << endl << "Tree 1 (from array): " << endl;
printTree(tree1);
int subTreeArray[] = {16, 11, 12, 21, 18, 19, 25};
cout << endl << endl << "Array 2: " << endl;
for (int i=0; i<7; i++) {
cout << subTreeArray[i] << " ";
}
BinaryTreeNode *tree2 = createBinaryTreeFromArray(subTreeArray, 7);
cout << endl << endl << "Tree 2 (from array): " << endl;
printTree(tree2);
cout << endl << endl << "Is tree2 a subtree of tree1?: " <<
(doesTree1ContainTree2(tree1, tree2)? "Yes" : "No") << endl;
delete(tree1);
delete(tree2);
}