Recursion 코드를 Implementation으로 고치려고 하는데

Datastructures를 공부 중인 학생인데요,

수업시간에 Tail Recursion을 Implemetation으로 바꿔보라는데 한참을 헤매다 결국 못했는데요,

보통 While로 고쳐서 쉽게 하던데 머리 속으로 생각해서 할려니 복잡해지기만하고, 해결이 안되서요..

밑에 두 개 였는데, Binary Search Tree 중 internal insert와 delete에 해동하는 부분이구요,

어떻게 해야하는거죠? (혹시 몰라 전체 소스 첨부해요)

/* (P7-4)==================== _insert ====================
This function uses recursion to insert the new data
into a leaf node in the BST tree.
Pre Application has called BST_Insert, which
passes root and data pointer
Post Data have been inserted
Return pointer to [potentially] new root
*/
NODE* _insert (BST_TREE* tree, NODE* root, NODE* newPtr)
{
// Statements
if (!root)
// if NULL tree
return newPtr;

// Locate null subtree for insertion
if (tree->compare(newPtr->dataPtr,
root->dataPtr) < 0)
{
root->left = _insert(tree, root->left, newPtr);
return root;
} // new < node
else
// new data >= root data
{
root->right = _insert(tree, root->right, newPtr);
return root;
} // else new data >= root data
return root;
} // _insert

/* (P7-6)==================== _delete ====================
Deletes node from the tree and rebalances
tree if necessary.
Pre tree initialized--null tree is OK.
dataPtr contains key of node to be deleted
Post node is deleted and its space recycled
-or- if key not found, tree is unchanged
Return success is true if deleted; false if not found
pointer to root
*/
NODE* _delete (BST_TREE* tree, NODE* root,
void* dataPtr, bool* success)
{
// Local Definitions
NODE* dltPtr;
NODE* exchPtr;
NODE* newRoot;
void* holdPtr;

// Statements
if (!root)
{
*success = false;
return NULL;
} // if

if (tree->compare(dataPtr, root->dataPtr) < 0)
root->left = _delete (tree, root->left,
dataPtr, success);
else if (tree->compare(dataPtr, root->dataPtr) > 0)
root->right = _delete (tree, root->right,
dataPtr, success);
else
// Delete node found--test for leaf node
{
dltPtr = root;
if (!root->left)
// No left subtree
{
free (root->dataPtr); // data memory
newRoot = root->right;
free (dltPtr); // BST Node
*success = true;
return newRoot; // base case
} // if true
else
if (!root->right)
// Only left subtree
{
newRoot = root->left;
free (dltPtr);
*success = true;
return newRoot; // base case
} // if
else
// Delete Node has two subtrees
{
exchPtr = root->left;
// Find largest node on left subtree
while (exchPtr->right)
exchPtr = exchPtr->right;

// Exchange Data
holdPtr = root->dataPtr;
root->dataPtr = exchPtr->dataPtr;
exchPtr->dataPtr = holdPtr;
root->left =
_delete (tree, root->left,
exchPtr->dataPtr, success);
} // else
} // node found
return root;
} // _delete