Binary Search Tree and Double-linked List - Interview Question&Answer

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.

For example, if we input a binary search tree as shown on the left side of the Figure 1, the output double-linked list is shown on the right side.

Figure 1: The conversion between a binary search tree and a sorted double-linked list

A node of binary search tree is defined in C/C++ is as:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Analysis: In a binary tree, each node has two pointers to its children. In a double-linked list, each node also has two pointers, one pointing to the previous node and the other pointing to the next one. Additionally, binary search tree is a sorted data structure. In a binary search tree, value in parent is always greater than value of its left child and less than value of its right child. Therefore, we can adjust a pointer to its left child in binary search tree to its previous node in a double-linked list, and adjust a pointer to its right child to its next node. 

It is required that the converted list should be sorted, so we can adopt in-order traversal. That is because according to the definition of in-order traversal we traverse from nodes with less value to nodes with greater value. When we reach the root of the binary tree in Figure1, the tree may be viewed as three parts: a root with value 10, a left sub-tree with root value 6 and a right sub-tree with root value 14. According to the definition of sorted double-linked list, the root node with value 10 should be linked to the node with the greatest value (the node with value 8) in its left sub-tree, and it should be also linked to the node with the least value (the node with value 12) in its right sub-tree, as shown in Figure 2.

Figure 2: A tree with three parts: root, left sub-tree, right sub-tree. After we can the left sub-tree and right sub-tree, and we link them with the root, and then we can get a sorted double-linked list

According to the definition of in-order traversal, the 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. How to convert its left sub-tree and right sub-tree? It should be similar to converting the whole tree. Therefore, we can solve it with recursion.

We can write the following code based on the recursive solution:

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);

}

In the code above, pLastNodeInList is the last node (also the node with the greatest value) in the converted double-linked list. When we reach the value with 10, its left sub-tree has already been converted, and pLastNodeInList points to the node with 8. Afterwards we connect the root node to the linked list, and the node with 10 becomes the last node in the list (new node with the greatest value), so we move the pointer pLastNodeInList to the node with 10. We continue to invoke the function recursively with parameter pLastNodeInList to convert the right sub-tree. After we reach the left most node in the right sub-tree (also the node with least value), we linked it to the node with 10 in the list.