Friday, September 9, 2011

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.
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.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.

17 comments:

  1. hi, why do we need to define pLastNodeInList as double pointer? will pointer work? thanks.

    ReplyDelete
    Replies
    1. The reason is that we are going to change where pLastNodeInList points. If the parameter is declared as *pLastNodeInList, we can only modify the content pointed by pLastNodeInList, but can't modify pLastNodeInList itself (make it point to other address).

      Delete
    2. we could have used BinaryTreeNode & *pLastNodeInList and then use pLastNodeInList as a single pointer in the function.

      Delete
  2. hi, I am curious that how you implement "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.", I can not find the corresponding code in your program. did you miss something after " ConvertNode(pCurrent->m_pRight, pLastNodeInList);"

    thanks,

    ReplyDelete
  3. we could have used BinaryTreeNode & *pLastNodeInList and then use pLastNodeInList as a single pointer in the function.

    ReplyDelete
  4. Here is another solution in java


    package com.smartdumpy.binaryTree;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;


    public class BST {

    /**
    * @param args
    */
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s ="";

    public static void main(String[] args) {
    // TODO Auto-generated method stub

    BST bst=new BST();
    //bst.createBSTSubTree(bst.root);

    bst.createBST();

    bst.BSTDisplay(bst.root,0);
    System.out.println("\nInOrder Traversal");
    bst.inOrder(bst.root);
    BTNode phead=null;
    phead=bst.binaryToDoublyLinkedList(bst.root,phead);
    if(phead!=null)
    {
    System.out.println("\nFrom start : ");
    while(phead.right!=null) {
    System.out.print(phead.info + " ");
    phead=phead.right;
    }
    System.out.print(phead.info + " ");

    System.out.println("\nFrom end : ");

    while(phead.left!=null)
    {
    System.out.print(phead.info + " ");
    phead=phead.left;
    }
    System.out.print(phead.info + " ");
    }
    }
    class BTNode {

    public BTNode (String value)
    {
    info=value;
    }
    String info;
    BTNode left;
    BTNode right;

    }

    private BTNode root;

    public void createBST()
    {

    root =new BTNode("10");
    root.left =new BTNode("6");
    root.right =new BTNode("14");

    root.left.left=new BTNode("4");
    root.left.left.left=new BTNode("2");
    root.left.left.right=new BTNode("5");
    root.left.right=new BTNode("8");

    root.right.left=new BTNode("12");
    root.right.right=new BTNode("16");
    }


    public void BSTDisplay(BTNode node, int numberOfSpace)
    {
    if(node!=null)
    {

    BSTDisplay( node.right, ++numberOfSpace);
    for (int i = 0; i < numberOfSpace; i++) {
    System.out.print(" ");
    }
    System.out.println(node.info + "\n\n");

    BSTDisplay( node.left, numberOfSpace);

    }
    }

    public void BST2SortedDoubleLinkedList(BTNode node)
    {

    }
    public BTNode getRightMostLeaf(BTNode node)
    {
    if(node !=null)
    while(node.right!=null)node=node.right;
    return(node);
    }

    public BTNode getLeftMostLeaf(BTNode node)
    {
    if(node!=null)
    while(node.left!=null)node=node.left;
    return(node);
    }

    public BTNode binaryToDoublyLinkedList(BTNode node, BTNode listHead)
    {

    if(node!=null)
    {

    if(node.left!=null )
    {
    listHead=binaryToDoublyLinkedList(node.left,listHead);
    BTNode getRightMostLeaf=getRightMostLeaf(node.left);
    getRightMostLeaf.right=node;
    node.left=getRightMostLeaf;
    if(listHead==null)
    {
    listHead=node.left;
    }
    }

    if(node.right!=null )
    {
    listHead=binaryToDoublyLinkedList(node.right,listHead);
    BTNode getLeftMostLeaf=getLeftMostLeaf(node.right);

    node.right=getLeftMostLeaf;
    getLeftMostLeaf.left=node;
    }
    }
    return listHead;

    }

    public void inOrder(BTNode node)
    {
    if(node!=null)
    {
    inOrder( node.left);
    System.out.print(node.info +" " );
    inOrder( node.right);

    }
    }

    }

    ReplyDelete
  5. Hi...what is the way to search an element in a double sorted linked list....with time complexity less then O(N).??

    ReplyDelete
  6. Can this code be done as :
    We keep deleting the root and keep inserting it again till the left child of the root becomes null.
    1) In the first step we will delete the root of the tree, definitely the root of the tree will be the successor of it and the successor will now become the root.
    2) Now the deleted node is inserted again, it will be inserted to the left of the (which was successor)root

    We will keep doing this till the left child of the root becomes null

    Java implementation:
    static BST treetolinkedlist(BST b)
    {
    while(b.root.getLeft()!=null)
    {
    Node x = b.Delete(b.root);
    b.insert(x.getData());
    }
    return b;
    }

    Correct me if i am wrong

    ReplyDelete
  7. It can be easily done with in order traversal algorithm.

    ReplyDelete
  8. Its simply superb.Feeling good to share the link to practicec# interview questions @ http://skillgun.com

    ReplyDelete
  9. Great problem! I came up with a simpler approach when I set out to solve the same problem: https://goo.gl/S8SFQt. Hope this helps someone.

    ReplyDelete
  10. Hi it may sound basic question but when current reaches left last node how does the node reaches its root?? for example in the diagram above if current is 4 then how does cotrol go to node 6? Please explain

    ReplyDelete
  11. Modified version, which will remove the extra traversal in tree to find the head node.

    BinaryTreeNode* ConvertNodeToDLL(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
    {
    if (pNode == NULL)
    return pNode;

    BinaryTreeNode *pCurrent = pNode;

    BinaryTreeNode *pHead = pCurrent;

    if (pCurrent->m_pLeft != NULL)
    pHead = ConvertNodeToDLL(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList;
    if (*pLastNodeInList != NULL)
    (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)
    ConvertNodeToDLL(pCurrent->m_pRight, pLastNodeInList);

    return pHead;
    }

    BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
    {
    BinaryTreeNode *pLastNodeInList = NULL;
    return ConvertNodeToDLL(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;
    }

    ReplyDelete
  12. A solution that does not require keeping track of the last node

    BinaryTreeNode* findMax(BinaryTreeNode* head) {
    if (head == nullptr)
    return nullptr;
    if (head->right == nullptr)
    return head;
    return findMax(head->right);
    }
    BinaryTreeNode* findMin(BinaryTreeNode* head) {
    if (head == nullptr)
    return nullptr;
    if (head->left == nullptr)
    return head;
    return findMin(head->left);
    }
    void convertToLinkedList(BinaryTreeNode* head) {
    if (head == nullptr)
    return;

    convertToLinkedList(head->left);
    convertToLinkedList(head->right);

    head->left = findMax(head->left);
    if (head->left != nullptr) {
    head->left->right = head;
    }

    head->right = findMin(head->right);
    if (head->right!=nullptr) {
    head->right->left = head;
    }
    }

    ReplyDelete
  13. Why do you check whether (*pLastNodeInList != NULL) before assigning (*pLastNodeInList)->m_pRight = pCurrent?

    Seems unnecessary, as pLastNodeInList would not be NULL at that stage.

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. Here is an alternate solution in java where we keep passing leftParent and rightParent and correct the left and right pointers. Let me know if you see any issue with this solution:

    class BSTToLinkedList
    {
    class Node {
    int value;
    Node leftNode;
    Node rightNode;

    public Node(int value) {
    this.value = value;
    this.leftNode = null;
    this.rightNode = null;
    }

    }

    public Node constructBST() {

    Node node1 = new Node(4);
    Node node2 = new Node(8);
    Node node3 = new Node(12);
    Node node4 = new Node(16);

    Node node5 = new Node(6);
    node5.leftNode = node1;
    node5.rightNode = node2;

    Node node6 = new Node(14);
    node6.leftNode = node3;
    node6.rightNode = node4;

    Node root = new Node(10);
    root.leftNode = node5;
    root.rightNode = node6;

    return root;
    }

    public void convertBSTToDLL(Node node, Node leftParent, Node rightParent) {

    if(node == null) {
    return;
    }


    convertBSTToDLL(node.leftNode, leftParent, node);

    convertBSTToDLL(node.rightNode, node, rightParent);

    if(node.leftNode == null && leftParent != null) {
    node.leftNode = leftParent;
    leftParent.rightNode = node;
    }

    if(node.rightNode == null && rightParent != null) {
    node.rightNode = rightParent;
    rightParent.leftNode = node;
    }

    }

    public static void main (String[] args) throws java.lang.Exception
    {
    BSTToLinkedList bstToLinkedList = new BSTToLinkedList();
    Node root = bstToLinkedList.constructBST();
    bstToLinkedList.convertBSTToDLL(root, null, null);

    while(root.leftNode != null) {
    root = root.leftNode;
    }

    while(root.rightNode != null) {
    System.out.print(root.value + " ");
    root = root.rightNode;
    }
    }
    }

    ReplyDelete