Coding Interview Questions: No. 01 - Binary Search Tree and Double-linked List

Question: Convert a binary search tree to a sorted double-linked list. We can only change the target of pointers, but cannot create any new nodes.

According to the definition of in-order traversal, the left sub-tree should be already converted to a sorted list when we reach its root (the node with value 10), and the last node in the sorted list should be the node with the greatest node (the node with value 8). If we link the last node in list to the root node of tree, then the root is the last node in list now. We continue to convert its right sub-tree, and connect the root to the node with its least value.

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)

{

    BinaryTreeNode *pLastNodeInList = NULL;

    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList points to the tail of double-linked list,

    // but we need to return its head

    BinaryTreeNode *pHeadOfList = pLastNodeInList;

    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)

        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;

}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)

{

    if(pNode == NULL)

        return;

    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != NULL)

        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList;

    if(*pLastNodeInList != NULL)

        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)

        ConvertNode(pCurrent->m_pRight, pLastNodeInList);

}

Read full article from Coding Interview Questions: No. 01 - Binary Search Tree and Double-linked List