Transform the binary search tree into a sorted two-way linked list

Question:
Transform the binary search tree into a sorted two-way linked list.
do not use recursion.
do not create any new node, only adjust the pointer to point.
10
/ \
6 14
/ \ / \
4 8 12 16
-->>
4=6=8=10=12=14=16

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

Answer:
inline BSTreeNode* eleminateMinNode(BSTreeNode** tree) {
BSTreeNode* treeHead = tree;
if (!treeHead)
return 0;
BSTreeNode treeHeadParent = 0;
while (treeHead->m_pLeft) {
treeHeadParent = treeHead;
treeHead = treeHead->m_pLeft;
}
if (treeHeadParent)
treeHeadParent->m_pLeft = treeHead->m_pRight;
if (treeHead == *tree)
*tree = treeHead->m_pRight;
return treeHead;
}

inline BSTreeNode* eleminateMaxNode(BSTreeNode** tree) {
BSTreeNode* treeHead = tree;
if (!treeHead)
return 0;
BSTreeNode treeHeadParent = 0;
while (treeHead->m_pRight) {
treeHeadParent = treeHead;
treeHead = treeHead->m_pRight;
}
if (treeHeadParent)
treeHeadParent->m_pRight = treeHead->m_pLeft;
if (treeHead == *tree)
*tree = treeHead->m_pLeft;
return treeHead;
}

void BSTreeToDoubleLinkChainInternal(BSTreeNode* tree, BSTreeNode** headp, BSTreeNode** tailp) {
if (!tree)
return;
BSTreeNode* tail = tree;
BSTreeNode* right = tail->m_pRight;
BSTreeNode* minRight = eleminateMinNode(&right);
while (minRight && minRight != tail) {
tail->m_pRight = minRight;
minRight->m_pLeft = tail;
tail = minRight;
minRight = eleminateMinNode(&right);
}
tail->m_pRight = 0;
BSTreeNode* left = tree->m_pLeft;
BSTreeNode* maxLeft = eleminateMaxNode(&left);
BSTreeNode* head = tree;
while (maxLeft && maxLeft != head) {
head->m_pLeft = maxLeft;
maxLeft->m_pRight = head;
head = maxLeft;
maxLeft = eleminateMaxNode(&left);
}
head->m_pLeft = 0;
*headp = head;
*tailp = tail;
}

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️