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);
}
Comments