Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.


If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:

i) an ordered binary tree (BST) storing numbers from 1 – 5.
ii) original tree converted to a sorted circular doubly-linked list. Its left and right pointers were modified to point to its previous and next node.

I originally read this interesting problem here: The Great Tree-List Recursion Problem.

Hint:
Think of in-order traversal. How do you ensure that the last element’s right pointer points back to the first element?

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

Solution:
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).

How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?

Alternative Solution:
There is an alternative solution which doesn’t use in-order traversal. Instead, it uses a divide and conquer method which is quite neat. I highly recommend you to read the solution (code provided) here.

VN:F [1.9.22_1171]
Rating: 4.5/5 (75 votes cast)
Convert Binary Search Tree (BST) to Sorted Doubly-Linked List, 4.5 out of 5 based on 75 ratings

46 thoughts on “Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

  1. Greed

    The solutions you provide are really very nice . I have a question and i am not able to solve it .Please help!!
    Question is “Vertical order traversal of a binary tree.”

    VA:F [1.9.22_1171]
    0
    1. S

      Vertical order means I believe its post order traversal. By using recursion the code can be as follows:

      public void postOrder(Node node)
      {
      if(node!=null)
      {
      postOrder(node.left);
      postOrder(node.right);
      sysout(node.value);
      }
      }

      If tree has following insertions:
      Root = 25
      insert(25,11)
      insert(25,15)
      insert(25,16)
      insert(25,23)
      insert(25,30)

      Then vertical order will print 23,16,15,11,30,25.

      VA:F [1.9.22_1171]
      -3
    1. ravenchen1204

      I have two solution
      sol one:
      run time O(N)
      space O(N)

      sol two:
      run time O(N^2)
      space O(1)

      if you are interested in those two solutions, let me no

      VA:F [1.9.22_1171]
      -9
  2. HX

    Another solution is to use post-order traverse. The idea is that for each node (considered as a sub tree), we find two pointers that point to its minimum and maximum child. Then we can make the linked list by:
    this_node->left_child->max —-> this_node;
    this_node-> —-> this_node->right_child->min;

    NOTE: I realize that the following code can generate a single link only. Need more thoughts how to modify it to generate double-linked list.

    VA:F [1.9.22_1171]
    0
  3. SkyWalker

    Hey 1337,

    I’ve tried an alternate solution, making use of a global node which keeps track of the last modified node.
    The code can be found here: http://collabedit.com/tknj8

    Please note, this doesn’t create a doubly sorted circular list.

    I wanted your thoughts about this solution and any possible bugs.

    Thanks.

    VA:F [1.9.22_1171]
    0
  4. Rvp

    Absolutely awesome!!! saw an alternate solution in stanford site but this is totally awesome

    Keep up the great work mate,cheers!!!

    VA:F [1.9.22_1171]
    0
  5. LoneShadow

    Wouldnt this work as well?

    void
    bsttodll(struct node *rootp, struct node **prevp, struct node **headp){
    if (!rootp) return;
    bsttodll(rootp->left, prevp, headp);
    rootp->left = *prevp;
    if (!*headp)
    *headp = rootp;
    if (*prevp)
    (*prevp)->right = rootp;
    *prevp = rootp;
    bsttodll(rootp->right, prevp, headp);
    }

    VA:F [1.9.22_1171]
    +1
  6. LoneShadow

    I guess it needs the special case, when recursion ends, the head and the final node need to be connected.

    VA:F [1.9.22_1171]
    0
  7. Pritam

    Hey I have written this code..but this does not give the correct output..
    e.g if tree is
    13
    8 20
    3 9 15 25

    output is – 13,20,25
    i.e head pointer n d right subtree..
    I don’t know why for left subtree elements, head is getting updated everytime..
    Please tell me what is the wrong thing in this..

    struct node *doubly(struct node *t,struct node *prev, struct node *head)
    {
    if(t==NULL)
    return;

    doubly(t->left,prev,head);
    t->left = prev;
    if(prev != NULL)
    prev->right=t;
    else
    head=t;
    struct node *right = t->right;
    head->left=t;
    t->right=head;
    prev = t;
    doubly(right,prev,head);
    return head;
    }

    treeToDoubly(struct node *t)
    {
    struct node *prev = NULL;
    struct node *head = NULL;
    head = doubly(t,prev,head);

    printf(“List is \n”);
    for(temp=head;temp->right!=head;temp=temp->right)
    printf(“%d,”,temp->data);
    printf(“%d”,temp->data);
    }

    VA:F [1.9.22_1171]
    0
  8. stormclass

    my solution is similar, but i think it is very easy to understand.

    class Solution {
    public:
    pair convertTreeRecursive(Node *root) {
    if (root == NULL) {
    return pair(NULL, NULL);
    }
    pair left = convertTreeRecursive(root->left);
    pair right = convertTreeRecursive(root->right);

    Node *prevLeft = left.first;
    Node *lastLeft = left.second;
    Node *prevRight = right.first;
    Node *lastRight = right.second;

    if (lastLeft) {
    lastLeft->right = root;
    root->left = lastLeft;
    }

    if (prevRight) {
    prevRight->left = root;
    root->right = prevRight;
    }

    return pair(prevLeft == NULL ? root : prevLeft,
    lastRight == NULL ? root : lastRight);
    }

    Node * convertTree(Node *root) {
    if (root == NULL) {
    return NULL;
    }
    pair ret = convertTreeRecursive(root);
    (ret.first)->left = ret.second;
    (ret.second)->right = ret.first;
    return ret.first;
    }
    };

    VA:F [1.9.22_1171]
    0
  9. Jinhui

    VN:F [1.9.22_1171]
    +1
  10. Pingback: Algorithm 3: Convert BST to Double Linked List | terribyte

  11. Pingback: Convert Binary Search Tree (BST) to Sorted Doubly-Linked List | This is how Cheng grows up

  12. LT

    VN:F [1.9.22_1171]
    0
  13. A

    VA:F [1.9.22_1171]
    0
  14. Prateek Caire

    Simple inorder will also solve the problem
    v = previously visited node
    h = head of doubly linked list

    VA:F [1.9.22_1171]
    +1
  15. lin17

    why don’t we just use top down approach?

    VN:F [1.9.22_1171]
    0
  16. Dan Gardner

    VA:F [1.9.22_1171]
    0
  17. sayannayak

    Hi 1337c0d3r,
    I was asked the same question.But the interviewer said inplace means we can’t use recursion because the stack space will be O(height). Is it possible to do it iteratively with only constant space

    VN:F [1.9.22_1171]
    0
  18. deb

    VA:F [1.9.22_1171]
    0
  19. deb

    void treeToDll(node *root, node **head, node **tail) {
    if (root == NULL)
    return;

    treeToDll(root->left, head, tail);

    /* head [] [] tail (root) */

    root->left = *tail; /* head [] [] tail right = root; /* head [] [] tail (root) */
    else
    *head = root; /* root */

    *tail = root; /* now root is tail of joined list */
    treeToDll(right, head, tail);
    }

    VA:F [1.9.22_1171]
    0
  20. yhqruc

    My first thought is not recursive method.
    Inorder traverse is enough.

    VA:F [1.9.22_1171]
    0
  21. shailesh

    I tried your solution and checked where the head points. When Left-most (smallest) node is a leaf then it points to second smallest left node. It only points correctly when the smallest node has a right child.

    (This is my observation correct me if im wrong)
    Reason:
    Consider the BST example above, the recursion stops when left most node is reached i.e 1 in above case. Now the first value to POP out of Stack is 1,null,null.
    So head = 1 , right = null (as p->right = null) , prev = 1 but the right recursion ( treeToDoublyList(root, prev, head); ) fails as right = null.

    So the next value to POP out of stack is 2,null,null.
    As prev is null , head = 2 (second smallest node)

    VA:F [1.9.22_1171]
    0
  22. Ajay

    how this is constant space… you are using recursion so space complexity will not be constant right??

    VA:F [1.9.22_1171]
    +1
  23. Margarette

    While cost is a minimum of three components; water proofing contractors.
    Radar system in which the worker services are offered work on the one
    to point out your AIA pay application form again and expecting
    different results. You might have waited till the last school bus job.
    The damage may need to be soliciting under the required
    services and areas in the detiails when it comes to roofing
    contractors. If your roof whether it s done nationwide through internet as these organizations accept members who
    they use, the seats, and don t want to work on houses.

    VA:F [1.9.22_1171]
    0
  24. simba518

    We can use a dumpy (safe) node, then we just need to track the previous (pre) node.

    VN:F [1.9.22_1171]
    +1
  25. garukun

    VA:F [1.9.22_1171]
    0
  26. Pingback: Important Data Structure And Algorithms To Prepare For Interview | Ankit Anand

  27. Rohit Singhal

    My simple solution to this problem…
    public void createDLL(TreeNode root, TreeNode[] head){
    if(root==null)
    return;
    createDLL(root.right, head);
    root.right = head[0];
    if(head[0]!=null)
    head[0].left = root;
    head[0] = root;
    createDLL(root.left, head);
    }

    VA:F [1.9.22_1171]
    0
  28. Brandon

    What is the space complexity of this algorithm? Since it is recursion version, is it space O(n) ? The problem asks for in-place solution, do you need to give a space O(1) solution?
    Thanks,

    VA:F [1.9.22_1171]
    0
  29. Anonymous

    VA:F [1.9.22_1171]
    +2
  30. shivam mitra

    The idea of saving the current node’s right pointer was amazing. I got the idea of updating the head but was loosing the current right node. I didn’t even think about saving it and using it. This idea was really good.

    VA:F [1.9.22_1171]
    0
  31. Anonymous

    Python code using generator

    VA:F [1.9.22_1171]
    0
  32. Boni

    Another divide and conquer approach. Recursive call returns head/tail for subtree rooted at n. Current node connects to left subtree’s tail, and right subtree’s head.

    VA:F [1.9.22_1171]
    0
  33. Ian

    divide and conquer in C++

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*