Below is given a header file and a source file of a Binary Search Tree. Inputs are 6 , 4, 2 , 5, 1, 3, 8, 7, 9

Simulate the recursion for in-order and post order traversal of BST. you have to provide the tracing of the call for both in and post order that how the traverse is happening. For an example, for pre_order,

1st call (passing the address of 6 and queue),

enqueue 6,

2nd call(passing the address of 4 and queue)

enqueue 4 3rd call 10th call return to 1st call........................................... till the end.

Therefore, please explain the tracing of calls for all the inputs for in-order and post-order from the code.

binarysearchtree.h #ifndef BINARYSEARCHTREE_H_INCLUDED #define BINARYSEARCHTREE_H_INCLUDED #include "quetype.h" template struct TreeNode { ItemType info; TreeNode* left; TreeNode* right; }; enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER}; template class TreeType { public: TreeType(); ~TreeType(); void MakeEmpty(); bool IsEmpty(); bool IsFull(); int LengthIs(); void RetrieveItem(ItemType& item, bool& found); void InsertItem(ItemType item); void DeleteItem(ItemType item); void ResetTree(OrderType order); void GetNextItem(ItemType& item, OrderType order, bool& finished); void Print(); private: TreeNode* root; QueType preQue; QueType inQue; QueType postQue; }; #endif // BINARYSEARCHTREE_H_INCLUDED binarysearchtree.cpp #include "binarysearchtree.h" #include "quetype.cpp" #include using namespace std; template TreeType::TreeType() { root = NULL; } template void Destroy(TreeNode*& tree) { if (tree != NULL) { Destroy(tree->left); Destroy(tree->right); delete tree; tree = NULL; } } template TreeType::~TreeType() { Destroy(root); } template void TreeType::MakeEmpty() { Destroy(root); } template bool TreeType::IsEmpty() { return root == NULL; } template bool TreeType::IsFull() { TreeNode* location; try { location = new TreeNode; delete location; return false; } catch(bad_alloc& exception) { return true; } } template int CountNodes(TreeNode* tree) { if (tree == NULL) return 0; else return CountNodes(tree->left) + CountNodes(tree->right) + 1; } template int TreeType::LengthIs() { return CountNodes(root); } template void Retrieve(TreeNode* tree, ItemType& item, bool& found) { if (tree == NULL) found = false; else if (item < tree->info) Retrieve(tree->left, item, found); else if (item > tree->info) Retrieve(tree->right, item, found); else { item = tree->info; found = true; } } template void TreeType::RetrieveItem(ItemType& item, bool& found) { Retrieve(root, item, found); } template void Insert(TreeNode*& tree, ItemType item) { if (tree == NULL) { tree = new TreeNode; tree->right = NULL; tree->left = NULL; tree->info = item; } else if (item < tree->info) Insert(tree->left, item); else Insert(tree->right, item); } template void TreeType::InsertItem(ItemType item) { Insert(root, item); } template void Delete(TreeNode*& tree, ItemType item) { if (item < tree->info) Delete(tree->left, item); else if (item > tree->info) Delete(tree->right, item); else DeleteNode(tree); } template void DeleteNode(TreeNode*& tree) { ItemType data; TreeNode* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); } } template void GetPredecessor(TreeNode* tree, ItemType& data) { while (tree->right != NULL) tree = tree->right; data = tree->info; } template void TreeType::DeleteItem(ItemType item) { Delete(root, item); } template void PreOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { Que.Enqueue(tree->info); PreOrder(tree->left, Que); PreOrder(tree->right, Que); } } template void InOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { InOrder(tree->left, Que); Que.Enqueue(tree->info); InOrder(tree->right, Que); } } template void PostOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { PostOrder(tree->left, Que); PostOrder(tree->right, Que); Que.Enqueue(tree->info); } } template void TreeType::ResetTree(OrderType order) { switch (order) { case PRE_ORDER: PreOrder(root, preQue); break; case IN_ORDER: InOrder(root, inQue); break; case POST_ORDER: PostOrder(root, postQue); break; } } template void TreeType::GetNextItem(ItemType& item, OrderType order, bool& finished) { finished = false; switch (order) { case PRE_ORDER: preQue.Dequeue(item); if(preQue.IsEmpty()) finished = true; break; case IN_ORDER: inQue.Dequeue(item); if(inQue.IsEmpty()) finished = true; break; case POST_ORDER: postQue.Dequeue(item); if(postQue.IsEmpty()) finished = true; break; } } template void PrintTree(TreeNode* tree) { if (tree != NULL) { PrintTree(tree->left); cout << tree->info << " "; PrintTree(tree->right); } } template void TreeType::Print() { PrintTree(root); }