1. What is the purpose of the function findParentNode? Why is the findNode not sufficient for this assignment?
2. Draw out (by hand or using ASCII art) the final version of the binary tree. This is after all insertions and deletions and insertions and such.
3. Code provided:
4. // Filename: BernardezBanegas_HW39.cpp

// Description: Simple Binary Tree

// Author: Alana Bernardez Banegas

// Date Modified: 11/30/2023

#include

using namespace std;

#include

/*

Fill out the code based off the attached template. I am giving you the functions to

use. You may choose a

different approach, but I would recommend at least using the provided code as a

starting point. Test your

program with the given driver. You are to insert nodes, display the tree a few

times, find some nodes,

delete some nodes, display the tree, insert some nodes again, and finally display

the tree again. I highly

recommend not doing everything thing at once! Comment out some of the code and test

things out as you code.

It is okay to pull command out entirely, just be sure your final product has the

full driver working.

When you turn in your code, also answer the following:

1. What is the purpose of the function findParentNode? Why is the findNode not

sufficient for this assignment?

2. Draw out (by hand or using ASCII art) the final version of the binary tree. This

is after all insertions

and deletions and insertions and such. (Hint: this is a very good thing to have

handy while you are writing

the program).

*/

struct TreeNode

{

int value; //or something else!

TreeNode *left;

TreeNode *right;

};

// Generally, pass by reference the pointers to the nodes!

int nodeValue(TreeNode *nodePtr);

void displayInOrder(TreeNode *nodePtr);

void displayPreOrder(TreeNode *nodePtr);

void displayPostOrder(TreeNode *nodePtr);

void insert(TreeNode *&nodePtr, TreeNode *&newNode);

void insertNode(TreeNode *&rootNode, int value);

TreeNode* findNode(TreeNode *&rootNode, int value);

TreeNode* findParentNode(TreeNode *&rootNode, int value);

void deleteNode(TreeNode *&rootNode, int value);

int main()

{

// Display a program heading

cout << "Binary Tree!" << endl << endl;

int tmpValue = 42;

string result;

TreeNode *tmpNode;

TreeNode *rootNode = new TreeNode;

// Initialize the contents of the node:

rootNode->value = tmpValue;

// Set the pointers to NULL:

rootNode->left = NULL;

rootNode->right = NULL;

// Now add some nodes...

insertNode(rootNode, 21);

insertNode(rootNode, 38);

insertNode(rootNode, 21);

insertNode(rootNode, 64);

insertNode(rootNode, 20);

insertNode(rootNode, 50);

insertNode(rootNode, 21);

insertNode(rootNode, 55);

insertNode(rootNode, 63);

insertNode(rootNode, 42);

insertNode(rootNode, 28);

insertNode(rootNode, 54);

insertNode(rootNode, 10);

insertNode(rootNode, 12);

insertNode(rootNode, 97);

cout << endl;

// Let's do some displays!

cout << "Displaying nodes in order: " << endl;

displayInOrder(rootNode);

cout << endl << endl;

cout << "Displaying nodes in PRE order: " << endl;

displayPreOrder(rootNode);

cout << endl << endl;

cout << "Displaying nodes in POST order: " << endl;

displayPostOrder(rootNode);

cout << endl << endl;

// Check to make sure the find function works...

tmpValue = 22;

tmpNode = findNode(rootNode, tmpValue);

result = (tmpNode != NULL) ? " WAS " : " NOT ";

cout << "Node " << tmpValue << result << "found!" << endl;

tmpValue = 20;

tmpNode = findNode(rootNode, tmpValue);

result = (tmpNode != NULL) ? " WAS " : " NOT ";

cout << "Node " << tmpValue << result << "found!" << endl;

cout << endl;

// Now for the deletion nodes... Make sure all variations work!

tmpValue = 52;

cout << "Attempting to delete node " << tmpValue << endl;

deleteNode(rootNode, tmpValue);

cout << endl;

tmpValue = 50;

cout << "Attempting to delete node " << tmpValue << endl;

deleteNode(rootNode, tmpValue);

cout << endl;

tmpValue = 97;

cout << "Attempting to delete node " << tmpValue << endl;

deleteNode(rootNode, tmpValue);

cout << endl;

tmpValue = 21;

cout << "Attempting to delete node " << tmpValue << endl;

deleteNode(rootNode, tmpValue);

cout << endl;

cout << "Displaying nodes in order: " << endl;

displayInOrder(rootNode);

cout << endl << endl;

// Add some nodes back, just for giggles...

insertNode(rootNode, 52);

insertNode(rootNode, 21);

insertNode(rootNode, 97);

cout << endl;

cout << "Displaying nodes in order: " << endl;

displayInOrder(rootNode);

cout << endl << endl;

// Thank the user (it is always good to be polite!)

cout << "Thank you!" << endl;

return 0;

}

/////////////////////////////////////////////////////////////////

// Display the value (whatever type it might be!!) of the node...

int nodeValue(TreeNode *nodePtr)

{

return nodePtr->value;

}

///////////////////////////////////////////////////////////

// Display the values in the subtree pointed to by nodePtr,

// via inorder traversal.

void displayInOrder(TreeNode *nodePtr)

{

if (nodePtr) // != NULL

{

displayInOrder(nodePtr->left);

cout << nodeValue(nodePtr)<< " ";

displayInOrder (nodePtr->right);

}

}

///////////////////////////////////////////////////////////

// Display the values in the subtree pointed to by nodePtr,

// via preorder traversal.

void displayPreOrder(TreeNode *nodePtr)

{

if (nodePtr) // != NULL

{

cout << nodeValue(nodePtr)<< " ";

displayPreOrder(nodePtr->left);

displayPreOrder (nodePtr->right);

}

}

///////////////////////////////////////////////////////////

// Display the values in the subtree pointed to by nodePtr,

// via postorder traversal.

void displayPostOrder(TreeNode *nodePtr)

{

if (nodePtr) // != NULL

{

displayPostOrder(nodePtr->left);

displayPostOrder(nodePtr->right);

cout << nodeValue(nodePtr)<< " ";

}

}

/////////////////////////////////////////////////////////////

// insert accepts a TreeNode pointer and a pointer to a node.

// The function inserts the node into the tree pointed to by

// the TreeNode pointer. This function is called recursively.

void insert(TreeNode *¤tNode, TreeNode *&newNode)

{

if (currentNode== NULL)

{

currentNode= newNode;

cout<< " Insert node value " << nodeValue(newNode) << endl;

}

else if (nodeValue(newNode) < nodeValue(currentNode))

{

insert(currentNode->left, newNode);

}

else if (nodeValue(newNode) > nodeValue(currentNode))

{

insert (currentNode->right, newNode);

}

else if (nodeValue(newNode) == nodeValue(currentNode))

{

cout << "Duplicate value found for " << nodeValue(newNode) << " Node not inserted " << endl;

delete newNode;

}

}

//////////////////////////////////////////////////////////

// insertNode creates a new node to hold num as its value,

// and passes it to the insert function.

void insertNode(TreeNode *&rootNode, int value)

{

TreeNode *newNode= NULL;

newNode= new TreeNode;

newNode->value = value;

newNode->left = NULL;

newNode->right = NULL;

insert(rootNode, newNode);

}

///////////////////////////////////////////////

// findNode determines if a value is present in

// the tree. If so, the function returns the node.

// Otherwise, it returns NULL.

TreeNode* findNode(TreeNode *&rootNode, int value)

{

TreeNode *nodePtr = rootNode;

while (nodePtr) //!= NULL

{

if (value == nodeValue(nodePtr))

return nodePtr;

else if (value < nodeValue(nodePtr))

nodePtr = nodePtr->left;

else // if(value > nodeValue(nodePtr))

nodePtr = nodePtr->right;

}

return NULL;

}

/////////////////////////////////////////////////////

// findParentNode determines if a value is present in

// the tree. If so, the function returns the parent of the node.

// Otherwise, it returns NULL.

// In order to find the answer you need to know findParentNode

TreeNode* findParentNode(TreeNode *&rootNode, int value)

{

TreeNode *nodePtr = rootNode;

while (nodePtr)

{

if (nodePtr->left != NULL && value == nodeValue(nodePtr->left))

return nodePtr;

else if (nodePtr->right != NULL && value == nodeValue(nodePtr->right))

return nodePtr;

nodePtr = nodePtr->left;

}

return NULL;

}

///////////////////////////////////////////////////////////////

// deleteNode finds the node in the tree that is to be deleted.

// The node is removed and the branches of the tree below

// the node are reattached.

// When the node has two children, be careful! Move up the node

// from the right side, and then the bottom leftmost node to

// repace the deleted node. This is the tricky part!!!

void deleteNode(TreeNode *&rootNode, int value)

{

bool isOnLeft;

TreeNode *nodePtr;

TreeNode *parentPtr = findParentNode (rootNode, value);

if (parentPtr == NULL)

{

cout << "Unable to find node " << value << endl;

return;

}

isOnLeft = (nodeValue(parentPtr->left) == value);

if (isOnLeft)

nodePtr = parentPtr->left;

else

nodePtr = parentPtr->right;

// node has no children

if(nodePtr->left == NULL && nodePtr == NULL)

{

cout << " Deleting node " << nodeValue(nodePtr) << " with no children "<< endl;

(isOnLeft? parentPtr->left : parentPtr->right) = NULL;

delete nodePtr;

nodePtr = NULL;

}

// delete node with only one child (left)

else if(nodePtr->left != NULL && nodePtr->right == NULL)

{

cout << " Deleting node " << nodeValue(nodePtr)<< " on the left side only " << endl;

(isOnLeft? parentPtr->left : parentPtr->right) = NULL;

delete nodePtr;

nodePtr = NULL;

}

// delete node with only one child (right)

else if(nodePtr->left == NULL && nodePtr->right != NULL)

{

cout << " Deleting node " << nodeValue(nodePtr)<< " on the right side only " << endl;

(isOnLeft? parentPtr->left : parentPtr->right) = NULL;

delete nodePtr;

nodePtr = NULL;

}

// node has two children

else

{

cout << "Deleting node " << nodeValue(nodePtr)<< " on both sides " << endl;

TreeNode *tmpPtr = nodePtr->right;

while (tmpPtr->left) // != NULL

{

tmpPtr = tmpPtr->left;

// Reattach the left dubtree to the bottom of the right side

tmpPtr->left = nodePtr->left;

// Reattach the right side to its place

(isOnLeft? parentPtr->left : parentPtr->right) = nodePtr->right;

delete nodePtr;

nodePtr = NULL;

}

}

}