Determine if a binary tree is a subtree of the other

by e2718281828459045

Question from CC150:
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 T1.
A tree T2 is a subtree of T1 if there exists a node in T1 such that the subtree of that node is identical to T2.

The algorithm is essentially the same as given in the book, except that I first preprocess the large tree to collect a set of subtrees whose size is the same as the small binary tree. The intuition is that since T2 is much smaller than T1, it is better to check the subtrees from lower levels (nodes at higher level might have too many nodes in their subtree, hence cannot match with T2). The extreme cases are complete binary trees and a linked-list like trees. The time complexity is O(n) + O(m) + O(n/m) \cdot O(m) = O(n+m), where n is the size of the large binary tree and m is the size of the small binary tree. The space complexity is O(n/m) for storing the roots of the possible subtrees from T1 that might match with T2.

#include "Binarytree.h"
#include <iostream>
#include <vector>
using namespace std;

int findcandidatesubtree(shared_ptr<Binarytree> root, int size, vector<shared_ptr<Binarytree>> &candidate)
{
    if (!root)
        return {};

    auto l = findcandidatesubtree(root->left, size, candidate);
    auto r = findcandidatesubtree(root->right, size, candidate);
    if (l + r + 1 == size)
        candidate.push_back(root);
    return l+r+1;
}

int subtreesize(shared_ptr<Binarytree> root)
{
    if (!root)
        return {};

    return subtreesize(root->left) + 1 + subtreesize(root->right);
}

bool issametree(shared_ptr<Binarytree> t1, shared_ptr<Binarytree> t2)
{
    if (!t1 && !t2)
        return true;
    else if (!t1 && t2 || t1 && !t2)
        return false;
    
    return (t1->key == t2->key) && issametree(t1->left, t2->left) && issametree(t1->right, t2->right);
}

shared_ptr<Binarytree> subtree(shared_ptr<Binarytree> root, shared_ptr<Binarytree> small)
{
    if (!small || !root)
        return {};

    vector<shared_ptr<Binarytree>> candidate;
    int smalltreesize = subtreesize(small);
    findcandidatesubtree(root, smalltreesize, candidate);
    for (auto i = candidate.begin(); i != candidate.end(); ++i)
        if (issametree(*i, small))
            return *i;
    return {};
}