Dynamic Programming - Find If A Given Tree Has Duplicate Sub-Tree (Part III)

1. Algorithm
This is an improvement of the solution on the previous blog, Dynamic Programming - Find If A Given Tree Has Duplicate Sub-Tree (Part II). The solution presented in Part II has to go though the entire tree to calculate the hash code for each node and then iterate over the hash map to find hash key with collisions to test node-by-node. This guarantees O(N) solution, where N is the size of the entire tree. However this problem needs only to find out if duplicate trees exist or not. There is no need to carry on computing the hash code for the entire tree, if one of duplication can be detected already.

The improvement is very straightforward. Compute the hash code for each node via  post-order traversal. When insert the hash key into the hash map, immediately test if collision exists. If yes, immediately test if the duplication of sub tree exist or not. If found duplication then stop calculating hash code and return true. Otherwise carry on computing the hash code for the rest the tree.

Pseudo-code:
1. Calculate the hash code for this node in the same way via post-order traversal
2. Insert into the hash code into the hash map
    * Insert into the hash map directly if hash code not present yet
    * Node-by-node comparison of this node against hash value entries if present already
        - Return true, if node-by-node comparison is true
        - Insert hash code into the hash map otherwise
3. Repeat Step 1 and Step 2 until exhaust the entire true
4. Return false

In the solution on Part II it guarantees linear solution and always linear, not more and not less. However this solution guarantees linear solution too. But slightly better in average. The worse case will be in the case that the only duplication happens in level 1 (root node - level 0). Otherwise in any other cases this solution does not require to calculate the entire tree. The best cases will be that the duplication sub-trees reside in the left part of the tree.

2. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
bool FindDuplicateTreeInEntries(const std::unordered_set<TreeNode<T>*> entries,
                                TreeNode<T>* refEntry,
                                TreeNode<T>* &entry1,
                                TreeNode<T>* &entry2)
{
    if (!MoreThanNNodes_R(refEntry, 2)) {
        return false;
    }
    auto itEnd = entries.end();
    for (auto it = entries.begin(); it != itEnd; ++it) {
        if (MoreThanNNodes_R(*it, 2) && CompareTwoTrees_R(*it, refEntry)) {
            entry1 = *it;
            entry2 = refEntry;
            return true;
        }
    }

    return false;
}

template <typename T>
size_t CalculateHashMapAndFindSubTree_R(TreeNode<T>* root,
    std::unordered_map<size_t, std::unordered_set<TreeNode<T>*>> &hm,
    TreeNode<T>* &entry1,
    TreeNode<T>* &entry2,
    bool &found)
{
    // Prime number used to calculate the hash code in Step 1
    const size_t PrimeOfCurNode = 1009;
    const size_t PrimeOfLeftNode = 2909;
    const size_t PrimeOfRightNode = 4021;

    // Return directly if duplication is found
    // Get out of recursion directly
    if (!root || found) {
        return 0;
    }

    size_t hashKey = *root->data * PrimeOfCurNode;
    if (root->left) {
        // Find in the left branch: Step 1 post-order traversal
        hashKey += PrimeOfLeftNode * CalculateHashMapAndFindSubTree_R(root->left,
                                                                      hm,
                                                                      entry1,
                                                                      entry2,
                                                                      found);
    }
    if (!found && root->right) {
        // Continue finding in the right branch: Step 1 post-order traversal
        hashKey += PrimeOfRightNode * CalculateHashMapAndFindSubTree_R(root->right,
                                                                       hm,
                                                                       entry1,
                                                                       entry2,
                                                                       found);
    }
    if (!found) {
        // Calculate hash code for the current root: Step 1 post-order traversal
        size_t hashValue = std::hash<size_t>{}(hashKey);
        auto foundIt = hm.find(hashValue);
        if (foundIt == hm.end()) {
            // Insert into hash map if not present yet: Step 2
            std::unordered_set<TreeNode<T>*> entry;
            entry.insert(root);
            hm.insert(std::make_pair(hashValue, entry));
        }
        else {
            std::unordered_set<TreeNode<T>*>& refEntry = foundIt->second;
            if (refEntry.find(root) == refEntry.end()) {
                // Node-by-node comparison: Step 2
                found = FindDuplicateTreeInEntries(refEntry, root, entry1, entry2);
                if (!found) {
                    // Insert into hash map if node-by-node comparison is false: Step 2
                    refEntry.insert(root);
                }
            }
        }
        // Return hash value for next calculation: Step 3
        return hashValue;
    }
    return 0;
}

template <typename T>
bool HaveDuplicateSubTree3_R(TreeNode<T> *root,
                                                      TreeNode<T>* &entry1,
                                                      TreeNode<T>* &entry2)
{
    std::unordered_map<size_t, std::unordered_set<TreeNode<T>*>> nodeHM;
    bool found = false;
    CalculateHashMapAndFindSubTree_R(root, nodeHM, entry1, entry2, found);
    return found;
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestFindDuplicateSubTree3()
{
    {
        TreeNode<int>* root = nullptr;
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
    }

    {
        const std::vector<int> testInput = { 1, 2 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->left);
        auto rightestNode = FindRightestNode(root->left);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 4);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput1 = { 100, 101, 102 };
        const std::vector<int> subTreeInput2 = { 102, 101, 100 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput1);
        auto subTree2 = ConstructTreeRecursive(subTreeInput2);
        assert(GetTreeSize_R(subTree1) == subTreeInput1.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput2.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->left = new TreeNode<int>(1001);
        subTree1->left->left = new TreeNode<int>(1002);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }
    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->left = new TreeNode<int>(1001);
        subTree1->right = new TreeNode<int>(1002);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->right = new TreeNode<int>(1002);
        subTree1->right->right = new TreeNode<int>(1001);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree3_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }
}

Dynamic Programming - Find If A Given Tree Has Duplicate Sub-Tree (Part II)

1. Problem Description

This blog entry is to present an alternative solution to the one proposed on Dynamic Programming - Find If A Given Tree Has Duplicate Sub-Tree (Part I). Please refer to it for the original problem.

The original idea is coming from one of my colleagues. When we were in the afternoon coffee, I mentioned what I usually do on the train and started to talk about this problem. My colleagues showed interest and one of them presented the idea of calculating the hash value of each node. And I further refined the solution and afterwards we had another brief discussion. (Just cannot image how smart they are.)

2. Algorithm

The idea is to calculate the hash code for each node and this hash value should have all information of its sub-tree. If there are duplicate sub-tree existing in the given tree, then two nodes must have the same hash value. But the same hash value does not guarantee the same sub-tree. It seems necessary to keep further node-by-node checking against those nodes calculated with the same hash value.

Pseudo-code:

1. For each node calculate the hash code

    - HashKey = 1009*currentNodeValue + 2909*HashValueOfLeft + 4021*HashValueOfRight

        * HashValueOfLeft = 0 if left child is not present

        * HashValueOfRight = 0 if right child is not present

        * Calculate the hash code based on HashKey

    - Use post-order traverse

2. Save the result into a hash map with <HashKey, HashSetOfTreeNode>

3. Go through the above hash map

    - Skip any sizeof(HashSetOfTreeNode) == 1

    - Otherwise check node-by-node of the entries in HashSetOfTreeNode

        * Skip entries that have less than 2 children

        * Return true if any two have exactly same nodes

4. Otherwise return false  

Prime number:

The reason why multiple different prime number (1009/2909/4021) with its value, HashValueOfLeft and HashValueOfRight is because it helps to remove the false entries. Example,

               1       |                                      1              |

          2            |                                           2         |

    3                  | Tree1                                     3     | Tree2

Tree1 has only left branch and Tree2 has only the right branch. Multiple left and right with different value will distinguish the left branch and right branch. This means that Tree1 and Tree2 are expected to have different hash value. (If multiply with the same value, the above example will expect Tree1 and Tree2 to have same hash value.) As for why choose 1009/2909/4021, it is arbitrary. The prime number seems well suited when hash function is involved.

But this does not remove all the possibility of different nodes but with same hash code. Just think of the equation of,

    1009*X+2909*Y+4021*Z = A, where X, Y and Z are variables and A is given number.

If A can be divided by (1009*2909*4021), there will be multiple solutions for X, Y and Z 

But 1009*2909*4021 is a really large number and the number of A (divisible by 1009*2909*4021) is relatively low. Choosing reasonable large prime numbers is expected to reduce the hash code collision.

3. C++ Implementation

// ********************************************************************************

// Implementation

// ********************************************************************************

template <typename T>

size_t CalculateHashMapOfTree_R(TreeNode<T>* root,

                                std::unordered_map<size_t,

                                std::unordered_set<TreeNode<T>*>> &hm)

{

    const size_t PrimeOfCurNode = 1009;

    const size_t PrimeOfLeftNode = 2909;

    const size_t PrimeOfRightNode = 4021;

    if (!root) {

        return 0;

    }

    // post-order traverse

    // Step 1 and 2

    size_t hashKey = *root->data * PrimeOfCurNode;

    if (root->left) {

        hashKey += PrimeOfLeftNode * CalculateHashMapOfTree_R(root->left, hm);

    }

    if (root->right) {

        hashKey += PrimeOfRightNode * CalculateHashMapOfTree_R(root->right, hm);

    }

    size_t hashValue = std::hash<size_t>{}(hashKey);

    auto foundIt = hm.find(hashValue);

    if (foundIt == hm.end()) {

        std::unordered_set<TreeNode<T>*> entry;

        entry.insert(root);

        hm.insert(std::make_pair(hashValue, entry));

    }

    else {

        std::unordered_set<TreeNode<T>*>& refEntry = foundIt->second;

        if (refEntry.find(root) == refEntry.end()) {

            refEntry.insert(root);

        }

    }

    return hashValue;

}

template <typename T>

bool FindDuplicateTreeInEntries(const std::unordered_set<TreeNode<T>*> entries,

                                TreeNode<T>* &entry1,

                                TreeNode<T>* &entry2)

{

    auto itEnd = entries.end();

    for (auto it = entries.begin(); it != itEnd; ++it) {

        auto itInner = it;

        ++itInner;

        for (; itInner != itEnd; ++itInner) {

            // enforce the rule of sub-tree

            if (MoreThanNNodes_R(*it, 2) && 

                MoreThanNNodes_R(*itInner, 2) && 

                CompareTwoTrees_R(*it, *itInner)) {

                entry1 = *it;

                entry2 = *itInner;

                return true;

            }

        }

    }

    return false;

}

template <typename T>

bool HaveDuplicateSubTree2_R(TreeNode<T> *root, TreeNode<T>* &entry1, TreeNode<T>* &entry2)

{

    std::unordered_map<size_t, std::unordered_set<TreeNode<T>*>> nodeHM;

    // Step 1 and 2: calculate the hash value and save it

    CalculateHashMapOfTree_R(root, nodeHM);

    auto itEnd = nodeHM.end();

    // Step 3: node-by-node check for those with same hash value

    for (auto it = nodeHM.begin(); it != itEnd; ++it) {

        std::unordered_set<TreeNode<T>*>& entryRef = it->second;

        if (FindDuplicateTreeInEntries(entryRef, entry1, entry2)) {

            return true;

        }

    }

    // Step 4

    return false;

}

// ********************************************************************************

// Test

// ********************************************************************************

void TestFindDuplicateSubTree2()

{

    {

        TreeNode<int>* root = nullptr;

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

    }

    {

        const std::vector<int> testInput = { 1, 2 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101 };

        auto subTree1 = ConstructTreeRecursive(subTreeInput);

        auto subTree2 = ConstructTreeRecursive(subTreeInput);

        assert(GetTreeSize_R(subTree1) == subTreeInput.size());

        assert(GetTreeSize_R(subTree2) == subTreeInput.size());

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);

        auto rightestNode = FindRightestNode(root);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 1);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };

        auto subTree1 = ConstructTreeRecursive(subTreeInput);

        auto subTree2 = ConstructTreeRecursive(subTreeInput);

        assert(GetTreeSize_R(subTree1) == subTreeInput.size());

        assert(GetTreeSize_R(subTree2) == subTreeInput.size());

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);

        auto rightestNode = FindRightestNode(root);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 1);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);

        assert(entry1 != nullptr);

        assert(entry2 != nullptr);

        assert(CheckTwoTreesWithSameValues(entry1, subTree1));

        assert(CheckTwoTreesWithSameValues(entry2, subTree2));

        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };

        auto subTree1 = ConstructTreeRecursive(subTreeInput);

        auto subTree2 = ConstructTreeRecursive(subTreeInput);

        assert(GetTreeSize_R(subTree1) == subTreeInput.size());

        assert(GetTreeSize_R(subTree2) == subTreeInput.size());

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->left);

        auto rightestNode = FindRightestNode(root->left);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 1);

        assert(*rightestNode->data == 4);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);

        assert(entry1 != nullptr);

        assert(entry2 != nullptr);

        assert(CheckTwoTreesWithSameValues(entry1, subTree1));

        assert(CheckTwoTreesWithSameValues(entry2, subTree2));

        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1;

        TreeNode<int>* entry2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };

        auto subTree1 = ConstructTreeRecursive(subTreeInput);

        auto subTree2 = ConstructTreeRecursive(subTreeInput);

        assert(GetTreeSize_R(subTree1) == subTreeInput.size());

        assert(GetTreeSize_R(subTree2) == subTreeInput.size());

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);

        auto rightestNode = FindRightestNode(root->right);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 6);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);

        assert(entry1 != nullptr);

        assert(entry2 != nullptr);

        assert(CheckTwoTreesWithSameValues(entry1, subTree1));

        assert(CheckTwoTreesWithSameValues(entry2, subTree2));

        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1 = nullptr;

        TreeNode<int>* entry2 = nullptr;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput1 = { 100, 101, 102 };

        const std::vector<int> subTreeInput2 = { 102, 101, 100 };

        auto subTree1 = ConstructTreeRecursive(subTreeInput1);

        auto subTree2 = ConstructTreeRecursive(subTreeInput2);

        assert(GetTreeSize_R(subTree1) == subTreeInput1.size());

        assert(GetTreeSize_R(subTree2) == subTreeInput2.size());

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);

        auto rightestNode = FindRightestNode(root->right);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 6);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        assert(entry1 == nullptr);

        assert(entry2 == nullptr);

        

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1 = nullptr;

        TreeNode<int>* entry2 = nullptr;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);

        subTree1->left = new TreeNode<int>(1001);

        subTree1->left->left = new TreeNode<int>(1002);

        TreeNode<int>* subTree2 = new TreeNode<int>(1000);

        subTree2->right = new TreeNode<int>(1001);

        subTree2->right->right = new TreeNode<int>(1002);

        assert(GetTreeSize_R(subTree1) == 3);

        assert(GetTreeSize_R(subTree2) == 3);

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);

        auto rightestNode = FindRightestNode(root->right);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 6);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        assert(entry1 == nullptr);

        assert(entry2 == nullptr);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1 = nullptr;

        TreeNode<int>* entry2 = nullptr;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);

        subTree1->left = new TreeNode<int>(1001);

        subTree1->right = new TreeNode<int>(1002);

        TreeNode<int>* subTree2 = new TreeNode<int>(1000);

        subTree2->right = new TreeNode<int>(1001);

        subTree2->right->right = new TreeNode<int>(1002);

        assert(GetTreeSize_R(subTree1) == 3);

        assert(GetTreeSize_R(subTree2) == 3);

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);

        auto rightestNode = FindRightestNode(root->right);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 6);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        assert(entry1 == nullptr);

        assert(entry2 == nullptr);

        DeleteTree(&root);

    }

    {

        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        auto root = ConstructTreeRecursive(testInput);

        assert(root != nullptr);

        assert(GetTreeSize_R(root) == testInput.size());

        TreeNode<int>* entry1 = nullptr;

        TreeNode<int>* entry2 = nullptr;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);

        subTree1->right = new TreeNode<int>(1002);

        subTree1->right->right = new TreeNode<int>(1001);

        TreeNode<int>* subTree2 = new TreeNode<int>(1000);

        subTree2->right = new TreeNode<int>(1001);

        subTree2->right->right = new TreeNode<int>(1002);

        assert(GetTreeSize_R(subTree1) == 3);

        assert(GetTreeSize_R(subTree2) == 3);

        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);

        auto rightestNode = FindRightestNode(root->right);

        assert(leftestNode != nullptr);

        assert(leftestNode->left == nullptr);

        assert(rightestNode != nullptr);

        assert(rightestNode->right == nullptr);

        assert(*leftestNode->data == 6);

        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;

        rightestNode->right = subTree2;

        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        assert(entry1 == nullptr);

        assert(entry2 == nullptr);

        DeleteTree(&root);

    }

}

Dynamic Programming - Find If A Given Tree Has Duplicate Sub-Tree (Part I)

1. Problem Description
This is a Google interview question for software develop engineer from careercup. Here is the original thread,
"

Find if a given binary tree has duplicate sub trees or not. 

(Two leaf nodes of a parent do not count as subtree)

- neer.1304 24 days ago in United States | Report Duplicate | Flag ".

2. Analysis
This is a tree structure problem and very naturally think of using recursive implementation (dynamic solution) is an intuitive option. I am going to use binary tree to illustrate the solution.

The idea is quite simple that find out if one duplicate sub-tree is located in the left branch and another is located in the right branch and keep the sub-problem of both left and right branch if it doesn't have.

F(Root) = true , if a sub-tree found in the left branch found in the right branch
             = false, if not and turn into a sub-problem of F(Root->left) and F(Root->right)

Pseudo-code
1. Find out if a sub-tree in left branch exists in the right branch
    * Return true, if yes
2. Root <= Root->left (sub-problem)
    * Repeat Step 1
3. Root <= Root->right (sub-problem)
    * Repeat Step 1
4. Return false if exhausted the whole tree and not found

How to achieve Step 1
A. Find out if LEFT(Root->left) can be found in RIGHT (Root->right)
    * Return true, if yes
B. Try LEFT->left can be found in RIGHT
    * Repeat Step A
C. Try LEFT->right can be found in RIGHT
    * Repeat Step A
D. Return false  if exhausted the whole LEFT and not found

How to achieve Step A
I. Compare "SubTree1" (as constant) from LEFT with RIGHT
    * Return ture, if yes
II. Try "SubTree1" with RIGHT->left
    * Repeat Step I
III. Try "SubTree1" with RIGHT->right
    * Repeat Step I
IV. Return false if exhausted the whole RIGHT and not found

The dynamic solution produces very clear and nice logic and code. But the complexity is very heavy and no optimization at all and literally it is to use the brute force to examine all the possibilities.

Note: as the discussion of the thread revealed that a single leaf node with its parent can't regarded a sub-tree, therefore any "Root" passed into including the sub-problem has to have at least 3 nodes (including itself).

3. C++ Implementation
The implementation is based on binary tree.
// ********************************************************************************
// Implementation
// ********************************************************************************
// compare two trees if have exactly values
template<typename T>
bool CompareTwoTrees_R(TreeNode<T>* lhs, TreeNode<T>* rhs)
{
    if (lhs == nullptr && rhs == nullptr) {
        return true;
    }
    if ((lhs == nullptr || rhs == nullptr) ||
        *lhs->data != *rhs->data) {
        return false;
    }
    return CompareTwoTrees_R(lhs->left, rhs->left) ||
           CompareTwoTrees_R(lhs->right, rhs->right);
}

template <typename T>
bool ContainSubTree_R(TreeNode<T> *base,
                      TreeNode<T>* sub,
                      TreeNode<T>* &entry1,
                      TreeNode<T>* &entry2)
{
    if (base == nullptr || sub == nullptr) {
        return false;
    }
    if (CompareTwoTrees_R(base, sub)) {
        entry1 = base;
        entry2 = sub;
        return true;
    }
    // Implementation of Step I
    return ContainSubTree_R(base->left, sub, entry1, entry2) ||
           ContainSubTree_R(base->right, sub, entry1, entry2);
}

template <typename T>
bool MoreThanNNodes_R(TreeNode<T>* root, const size_t N, size_t &curSize)
{
    if (curSize > N) {
        return true;
    }
    if (!root) {
        return false;
    }

    ++curSize;
    return MoreThanNNodes_R(root->left, N, curSize) ||
           MoreThanNNodes_R(root->right, N, curSize);
}

template <typename T>
bool MoreThanNNodes_R(TreeNode<T>* root, const size_t N)
{
    // Implementation of comparing the nodes in the tree against a size
    size_t curSize = 0;
    return MoreThanNNodes_R(root, N, curSize);
}

template <typename T>
bool FindCommonTree_R(TreeNode<T>* base1,
                      TreeNode<T>* base2,
                      TreeNode<T>* &entry1,
                      TreeNode<T>* &entry2)
{
    // sub-problems have to have at least 3 nodes
    if (!MoreThanNNodes_R(base1, 2) || !MoreThanNNodes_R(base2, 2)) {
        return false;
    }
    // Implementation of Step A
    return ContainSubTree_R(base1, base2, entry1, entry2) ||
           FindCommonTree_R(base1, base2->left, entry1, entry2) ||
           FindCommonTree_R(base1, base2->right, entry1, entry2);
}

template <typename T>
bool HaveDuplicateSubTree_R(TreeNode<T> *root, TreeNode<T>* &entry1, TreeNode<T>* &entry2)
{
    if (root == nullptr) {
        return false;
    }
    // Implementation of Step 1
    return FindCommonTree_R(root->left, root->right, entry1, entry2) ||
           HaveDuplicateSubTree_R(root->left, entry1, entry2) ||
           HaveDuplicateSubTree_R(root->right, entry1, entry2);
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestFindDuplicateSubTree()
{
    {
        TreeNode<int>* root = nullptr;
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
    }

    {
        const std::vector<int> testInput = { 1, 2 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->left);
        auto rightestNode = FindRightestNode(root->left);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 4);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }
}