Create a function called isSameTree

[Lacy9265]

Create a function called bool isSameTree that will take an argument of a tree. It will return a true if the argument is the equivalent tree or return false if the the two tree's are not equivalnet. I have written all the code for class except the isSameTree function. Could someone guide me on how I compare the trees. I have include a file called BinaryTee.cpp in this.

#include "BinaryTree.h"
#include <iostream>
#include <vector>

void BinaryTree::destroySubTree(TreeNode*& nodePtr)
{
    if (nodePtr)
    {
        if (nodePtr->left)
            destroySubTree(nodePtr->left);
        if (nodePtr->right)
            destroySubTree(nodePtr->right);
        delete nodePtr;

        nodePtr = nullptr;
    }
}

void BinaryTree::insert(TreeNode*& nodePtr, TreeNode*& newNode)
{
    if (nodePtr == nullptr)
        nodePtr = newNode;
    else if (newNode->value < nodePtr->value)
        insert(nodePtr->left, newNode);
    else
        insert(nodePtr->right, newNode);
}

void BinaryTree::insert(int number)
{
    TreeNode* newNode = new TreeNode;

    newNode->value = number;
    newNode->right = newNode->left = nullptr;

    // Insert newNode into tree
    insert(root, newNode);
}

void BinaryTree::displayInOrder(TreeNode* nodePtr)
{
    if (nodePtr)
    {
        displayInOrder(nodePtr->left);
        cout << nodePtr->value << endl;
        displayInOrder(nodePtr->right);
    }
}

void BinaryTree::displayInOrderWithLevel(TreeNode* nodePtr, int level)
{
    if (nodePtr)
    {
        displayInOrderWithLevel(nodePtr->left, level + 1);
        for (int index = 0; index < level; index++)
            cout << "\t";
        cout << nodePtr->value << endl;
        displayInOrderWithLevel(nodePtr->right, level + 1);
    }
}


void BinaryTree::displayPostOrder(TreeNode* nodePtr)
{
    if (nodePtr)
    {
        displayPostOrder(nodePtr->left);
        displayPostOrder(nodePtr->right);
        cout << nodePtr->value << endl;
    }
}

void BinaryTree::displayPreOrder(TreeNode* nodePtr)
{
    if (nodePtr)
    {
        cout << nodePtr->value << endl;
        displayPreOrder(nodePtr->left);
        displayPreOrder(nodePtr->right);
    }
}

void BinaryTree::displayInOrder()
{
    displayInOrder(root);
}

void BinaryTree::displayInOrderWithLevel()
{
    displayInOrderWithLevel(root, 0);
}

void BinaryTree::displayPreOrder()
{
    displayPreOrder(root);
}

void BinaryTree::displayPostOrder()
{
    displayPostOrder(root);
}

bool BinaryTree::search(int number)
{
    TreeNode* nodePtr = root;

    while (nodePtr)
    {
        if (nodePtr->value == number)
            return true;
        else if (number < nodePtr->value)
            nodePtr = nodePtr->left;
        else
            nodePtr = nodePtr->right;
    }

    return false;
}

void BinaryTree::deleteNode(int number, TreeNode*& nodePtr)
{
    if (number < nodePtr->value)
        deleteNode(number, nodePtr->left);
    else if (number > nodePtr->value)
        deleteNode(number, nodePtr->right);
    else
        makeDeletion(nodePtr);
}

void BinaryTree::makeDeletion(TreeNode*& nodePtr)
{
    // Define a temporary pointer to use in reattaching the left subtree
    TreeNode* tempNodePtr = nullptr;

    if (nodePtr == nullptr)
        cout << "Cannot delete an empty node" << endl;
    else if (nodePtr->right == nullptr) // reattach the left child
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->left;
        delete tempNodePtr;
    }
    else if (nodePtr->left == nullptr) // reattach the right child
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right;
        delete tempNodePtr;
    }
    // if the node has two children
    else
    {
        // move one node to the right.
        tempNodePtr = nodePtr->right;

        // Go to the end left node
        while (tempNodePtr->left)
            tempNodePtr = tempNodePtr->left;

        // reattach the left subtree
        tempNodePtr->left = nodePtr->left;
        tempNodePtr = nodePtr;

        // reattach the right subtree
        nodePtr = nodePtr->right;

        delete tempNodePtr;
    }
}

void BinaryTree::remove(int number)
{
    deleteNode(number, root);
}

void BinaryTree::balance()
{
    if (root != nullptr)
    {
        vector<int> vectorRecord;
        toVector(&vectorRecord);
        destroySubTree(root);
        balance(vectorRecord, 0, vectorRecord.size() - 1);
    }
}

void BinaryTree::balance(vector<int> vectorRecord, int start, int stop)
{
    int middle = (start + stop) / 2;

    if (start == stop)
    {
        insert(vectorRecord[middle]);
    }
    else if (start < stop)
    {
        insert(vectorRecord[middle]);
        balance(vectorRecord, start, middle - 1);
        balance(vectorRecord, middle + 1, stop);
    }
}


void BinaryTree::toVector(vector<int>* vectorRecord)
{
    toVector(vectorRecord, root);
}

void BinaryTree::toVector(vector<int>* vectorRecord, TreeNode* subTree)
{
    if (subTree != nullptr)
    {
        toVector(vectorRecord, subTree->left);
        vectorRecord->push_back(subTree->value);
        toVector(vectorRecord, subTree->right);
    }
}

// Need help on this function
bool BinaryTree::isSameTree(BinaryTree* anotherTree)
{
    return false;
}

[seeplus]

Well as you have .toVector(), one easy way would be to obtain the vector for the current tree, and the vector for the specified anotherTree and then compare these vectors (== is defined for vector).

[Lacy9265]

How would I call on the toVector for anotherTree and currentTree?

[seeplus]

Also, why is vectorRecord passed by pointer and not by ref?

How would I call on the toVector for anotherTree and currentTree?

Not tried, but something like:

bool BinaryTree::isSameTree(BinaryTree* anotherTree)
{
    vector<int> t1, t2;

    toVector(&t1);
    toVector(&t2, anotherTree->root);

    return t1 == t2;
}

[Lacy9265]

Okay, got it working. Thanks for your help.