CareerCup4.8.cpp

CareerCup4.8.cpp

/*
 Chapter 4
 
 4.8  You have two very large binary tree: 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 exist a node n in T1 such that the subtree of n is identical
 to T2. That is, if you cut off the tree at node n, the tow trees would be identical.
 */

/*
 Note: We don't use pre-order or in-order to see it two tree is identical because both trees are very large,
 whereas these traversal way require extra space to store.
 */

#include <iostream>

using namespace std;

//-------------------
// Tree node struct
//-------------------
typedef struct tNode {
    int value;
    struct tNode* left;
    struct tNode* right;
}tNode;

tNode* newNode(int v)
{
    tNode* node = new tNode;
    node->value = v;
    node->left = NULL;
    node->right = NULL;
    return node;
}

//--------------------------------
// Check Fuctions
//--------------------------------
// Check if two trees are match(order and value, not address)
bool isIdentical(tNode* m, tNode* n)
{
    // Both empty
    if (!m && !n)
        return true;
    // One of them is empty
    if (!m || !n)
        return false;
    if (m->value == n->value)
        return isIdentical(m->left, n->left) && isIdentical(m->right, n->right);
    else
        return false;
}

// Check if T2 is a subtree of T1
bool isSubtree(tNode* t1, tNode* t2)
{
    // Error: T1 is empty, no subtree
    if (!t1)
        return false;
    // T2 is empty, T2 always a subtree
    if (!t2)
        return true;
    // Find a node in T1, whose value is
    // equal to the value of root in T2
    if (t1->value == t2->value)
        if (isIdentical(t1, t2))
            return true;           /*
                                    Note: cannot just return isIdentical(t1, t2),
                                    since it will return intersection of all
                                    the recursive boolean values. We need to
                                    check isIdentical() everytime t1->value
                                    is equal to t2->value, once found, return
                                    true to exit. Else continue searching.
                                    */
    // Recursively find
    return isSubtree(t1->left, t2) || isSubtree(t1->right, t2);
}

//-------------------
// Utility Functions
//-------------------
// Generate T1
tNode* T1()
{
    /*      5
          /   \
        3      10
       / \    /
      1   4  7      */
    tNode* root = newNode(5);
    tNode* a = newNode(1);
    tNode* b = newNode(3);
    tNode* c = newNode(4);
    tNode* d = newNode(10);
    tNode* e = newNode(7);
    root->left = b; root->right = d;
    b->left = a; b->right = c;
    d->left = e;
    return root;
}
// Generate T2
tNode* T2()
{
    /*
       3
      / \
     1   4    */
    tNode* root = newNode(3);
    tNode* l = newNode(1);
    tNode* r = newNode(4);
    root->left = l; root->right = r;
    return root;
}

// Main Function to test
int main()
{
    tNode* t1 = T1();
    tNode* t2 = T2();
    // tNode* t2 = NULL;  // test empty
    bool sub = isSubtree(t1, t2);
    if (sub)
        cout << "T2 is a subtree of T1." << endl;
    else
        cout << "No. Believe me!" << endl;
    return 0;
}