BTS - Detect If Two Trees Have the Same Elements (Amazon Interview Question)

1. Problem Description
This originally an Amazon interview question for software development engineer from careercup. Here is the thread,
"

Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
ex-
Tree1:
5
1 6
5 4 3 6

Tree2:
1
3 4
6 5
have identical integers.

- teli.vaibhav 21 days ago in United States | Report Duplicate | Flag "

2. Implementation
The idea is quite simple that it is to use hash table to take all the elements from the first tree and then check if the second tree has exactly same elements as in the hash table. There is no special about the algorithm but I am going to demonstrate how to use recursive (in some sort of function programming sense) functions to implement the solution. Because tree structure is a very good source to understand functional programming particularly in the sense of sub-problem.

// ********************************************************************************
// Implementation
// ********************************************************************************
#include <memory>
#include <queue>
#include <stack>
#include <vector>
#include <unordered_map>

template<typename T>
struct TreeNode
{
    TreeNode(const T& d)
    : data(new T(d)), left(nullptr), right(nullptr)
    {}
    ~TreeNode()
    {
        std::shared_ptr<T>().swap(data);
    }

    std::shared_ptr<T> data;
    TreeNode* left;
    TreeNode* right;
};

template<typename T>
void ConstructTreeRecursive(const std::vector<T>& input,
                                         int startIndex,
                                         int endIndex,
                                         TreeNode<T>** node)
{
    if (startIndex > endIndex) {
        *node = nullptr;
        return;
    }

    const int curIndex = (startIndex + endIndex) >> 1;
    *node = new TreeNode<T>(input[curIndex]);
    ConstructTreeRecursive(input,
                           startIndex,
                           curIndex - 1,
                           &(*node)->left);
    ConstructTreeRecursive(input,
                           curIndex + 1,
                           endIndex,
                           &(*node)->right);
}

template<typename T>
TreeNode<T>* ConstructTreeRecursive(const std::vector<T>& input)
{
    if (input.empty()) {
        return nullptr;
    }

    TreeNode<T>* root = nullptr;
    ConstructTreeRecursive(input, 0, input.size() - 1, &root);
    return root;
}

template<typename T>
void GetUniqueElementsOfTree(const TreeNode<T>* tree,
                             std::unordered_map<T, bool>& values)
{
    if (tree == nullptr) {
        return;
    }

    if (values.find(*tree->data) == values.end()) {
        values[*tree->data] = false;
    }

    GetUniqueElementsOfTree(tree->left, values);
    GetUniqueElementsOfTree(tree->right, values);
}

template<typename T>
bool CheckTreeAgainstValues(const TreeNode<T>* tree,
                            std::unordered_map<T, bool>& values)
{
    if (tree == nullptr) {
        // hit here, not exactly sure if two trees match
        // because the 2nd tree could have less elements
        // then have to go through the entire hash table
        // to check if any element missing in the 2nd tree
        return true;
    }

    if (values.find(*tree->data) == values.end()) {
       // if an element does not appear in the first tree,
       // then the answer is false.
        return false;
    }
    else {
       // An element appears in both trees.
        values[*tree->data] = true;
    }

    bool result = CheckTreeAgainstValues(tree->left, values);
    if (result) {
        // carry on to exhaust the rest of the 2nd tree
        result = CheckTreeAgainstValues(tree->right, values);
    }

    return result;
}

template<typename T>
bool CheckTwoTreesWithSameValues(const TreeNode<T>* left, const TreeNode<T>* right)
{
    using HashMap = std::unordered_map<T, bool>;
    HashMap leftValues;
    GetUniqueElementsOfTree(left, leftValues);

    if (CheckTreeAgainstValues(right, leftValues)) {
        // check if all the elements appear in the 2nd tree or not.
        auto iterEnd = leftValues.end();
        for (auto iter = leftValues.begin(); iter != iterEnd; ++iter)
        {
            if (!iter->second) {
                // an element missing in the 2nd tree
                return false;
            }
        }
        // two trees match
        return true;
    }
 
    // an element missing in the 1st tree
    return false;
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestCasesOfCheckTwoTreesWithSameElements()
{
    const std::vector<int> testInput1 = { 1, 3, 5, 7, 2, 4, 6, 8 };
    auto tree1 = ConstructTreeRecursive(testInput1);
    assert(tree1 != nullptr);

    {
        TreeNode<int>* invalid1 = nullptr;
        TreeNode<int>* invalid2 = nullptr;

        assert(CheckTwoTreesWithSameValues(invalid1, invalid2) == true);
        assert(CheckTwoTreesWithSameValues(tree1, invalid2) == false);
        assert(CheckTwoTreesWithSameValues(invalid1, tree1) == false);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 1, 5, 2, 4 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
        DeleteTree(&tree2);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == true);
        DeleteTree(&tree2);
    }

    {
        const std::vector<int> testInput2 = { 1, 3, 5, 7, 2, 4, 6, 8, 1, 3, 5, 7, 2, 4, 6, 8, 9 };
        auto tree2 = ConstructTreeRecursive(testInput2);
        assert(tree2 != nullptr);
        assert(CheckTwoTreesWithSameValues(tree1, tree2) == false);
        DeleteTree(&tree2);
    }

    DeleteTree(&tree1);
}