Check Subtree

4.10 Check Subtree: Tl and T2 are two very large binary trees, with Tl much bigger than T2. Create an algorithm to determine if T2 is a subtree of Tl. A tree T2 is a subtree of T1 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.

Method 1:

• With this method, I am using the idea that within a preorder traversal, a subtree exists if within said tranversal exists the consecutive sequence of values of the subtree.

• However, we must indicate null elements in the tree because in doing so we preverse the entire uniqueness of a tree. Then we compare two preorder traversals with the null elements included, we ensure a subtree exists when they both preserve the same values and null elements.

template<typename iter>
bool isEqual(iter main_start, vector<int> &nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (*(main_start + i) != nums.at(i)) {
            return false;
        }
    }
    return true;
}

// testing if nums2 is subarray of nums1
bool isSubArray(vector<int> &main, vector<int> &nums) {
    for (int j = 0; j < main.size() - nums.size() + 1; j++)
        if (isEqual(main.begin() + j, nums))
            return true;

    return false;
}

void preOrderTrav(Node *root, vector<int> &ar) {
    if (!root) {
        ar.push_back(INT_MAX);
        return;
    }
    ar.push_back(root->value);
    preOrderTrav(root->left, ar);
    preOrderTrav(root->right, ar);
}

bool isSubtree(Node *root1, Node *root2) {

    vector<int> tree1, tree2;
    preOrderTrav(root1, tree1);
    preOrderTrav(root2, tree2);

    print(tree1);
    print(tree2);

    return isSubArray(tree1, tree2);
}

• Disadvantages:

  • O(N) to traverse, O(N) extra memory, and then O(N^2) to check subarray.

  • Lets try and get rid of that N^2!

• Method 2:

  • This method checks to see whether or two trees are the same on the basis that their addresses are the same. So while it doesnt work with two independent trees, it will work with the same tree.

  • O(N) time and space.

  • I've modified the subtree comparison by simply finding first element of the preorder tranversal of the second tree, and then confirming the remainder of the sequence. This will work with duplicate elements, since the addresses are unique.

template<typename iter>
bool isEqual(iter main_start, vector<Node*> &nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (&(*(main_start + i)) != &nums.at(i)) {
            return false;
        }
    }
    return true;
}

int find(vector<Node*> &nums, Node* findthis) {
    for (int i = 0; i < nums.size(); i++) {
        if (&nums.at(i) == &findthis) {
            return i;
        }
    }
    return INT_MAX;
}

// testing if nums2 is subarray of nums1
bool isSubArray(vector<Node*> &main, vector<Node*> &nums) {
    int index = find(main, nums.at(0));
    if (index == INT_MAX) return false;
    else {
        // confirm the rest of the sequence
        return isEqual(main.begin() + index, nums);
    }
}

void preOrderTrav(Node *root, vector<Node*> &ar) {
    if (!root) {
        ar.push_back(nullptr);
        return;
    }
    ar.push_back(root);
    preOrderTrav(root->left, ar);
    preOrderTrav(root->right, ar);
}

bool isSubtree(Node *root1, Node *root2) {

    vector<Node*> tree1, tree2;
    preOrderTrav(root1, tree1);
    preOrderTrav(root2, tree2);

    print(tree1);
    print(tree2);

    return isSubArray(tree1, tree2);
}

• To make this work with two independent subtrees, I've modified it to take in the values instead.

• This may not work with nodes in a tree that contain duplicate elements!

template<typename iter>
bool isEqual(iter main_start, vector<int> &nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (*(main_start + i) != nums.at(i)) {
            return false;
        }
    }
    return true;
}

int find(vector<int> &nums, int findthis) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums.at(i) == findthis) {
            return i;
        }
    }
    return INT_MIN;
}

// testing if nums2 is subarray of nums1
bool isSubArray(vector<int> &main, vector<int> &nums) {
    int index = find(main, nums.at(0));
    if (index == INT_MIN) return false;
    else {
        // confirm the rest of the sequence
        return isEqual(main.begin() + index, nums);
    }
}

void preOrderTrav(Node *root, vector<int> &ar) {
    if (!root) {
        ar.push_back(INT_MAX);
        return;
    }
    ar.push_back(root->value);
    preOrderTrav(root->left, ar);
    preOrderTrav(root->right, ar);
}

bool isSubtree(Node *root1, Node *root2) {

    vector<int> tree1, tree2;
    preOrderTrav(root1, tree1);
    preOrderTrav(root2, tree2);

    print(tree1);
    print(tree2);

    return isSubArray(tree1, tree2);
}