Convert Sorted List to Balanced Binary Search Tree (BST)

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


If you have not checked out my previous post: Convert Sorted Array to Balanced Binary Search Tree (BST), you should check it out now as this solution is built upon the previous solution.

Things get a little more complicated when you have a singly linked list instead of an array. Please note that in linked list, you no longer have random access to an element in O(1) time.

Singly-linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.

Naive Solution:
A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).

Hint:
How about inserting nodes following the list’s order? If we can achieve this, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.

Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

VN:F [1.9.22_1171]
Rating: 4.6/5 (155 votes cast)
Convert Sorted List to Balanced Binary Search Tree (BST), 4.6 out of 5 based on 155 ratings

80 thoughts on “Convert Sorted List to Balanced Binary Search Tree (BST)

  1. Anonymous

    Pretty darn smart and clean.
    I wonder if there is an iterative version, since you have the size n, you can literally scratch out the tree.(knowing exactly where nodes should be placed).

    VA:F [1.9.22_1171]
    0
    1. tk

      Yes, there is iterative solution. This solution is actually in-order traversing the balanced BST. As we have iterative solution for in-order traversal, we can solve this problem iteratively.

      VA:F [1.9.22_1171]
      +1
  2. Holger Dürer

    Now, is there a version as neat and tidy as this which does not require you to know the length of the list beforehand?

    VA:F [1.9.22_1171]
    -2
    1. Anonymous

      If there could have been one such algo in O(N) then why would avl tree insertion take O(NlogN) for inserting N elements (and suppose N is not known).
      Hence we need to know the value of N in advance along with the data.
      It is similar to buildHeap where build Heap takes O(N) if all numbers are given aprior . But in our case we have numbers in sorted order.

      VA:F [1.9.22_1171]
      +1
    2. data

      As the algorithm in O(n), we only add a constant factor by iterating over the list once to get its length. Therefore, knowing the length or not is (mostly) irrelevant.

      VA:F [1.9.22_1171]
      0
  3. abayley

    I see that the *&list parameter is modified. Wondering if there is a solution that does not modify *&list e.g. for languages like Haskell?

    VA:F [1.9.22_1171]
    0
  4. godheadatomic

    An iterative approach would be to traverse the list in order, and at each node insert into your new binary tree and rebalance (rotate) if necessary. This would work for a list of unknown length.

    VA:F [1.9.22_1171]
    0
  5. 1337c0d3r

    @Anonymous:
    The solution is highly recursive and definitely isn't a simple tail recursion, therefore converting it to an iterative one is definitely non-trivial.

    However, I have an iterative solution in mind.

    Since we know the size n, we already know the height of the tree, and how many leaves the tree has (ie, how many nodes at the bottom level).

    We first create an empty tree with the correct structure, then do an iterative in-order traversal of the tree setting values into the nodes as we traverse the list. The overall complexity is still O(N).

    VA:F [1.9.22_1171]
    +19
    1. ying

      Don’t need inorder traversal actually. We can create a pointer array which store pointer to every node. Then you only need N. Inorder Traversal best case is O(N), but larger than 1N.

      VA:F [1.9.22_1171]
      -2
  6. 1337c0d3r

    @Holger:
    Without knowing the length of the list, you wouldn't know how the balanced tree structure is like, since you don't know its height and such. You have to re-balance the tree each time you insert an element, which complexity is O(log(N)).

    VA:F [1.9.22_1171]
    0
    1. Xiaoguang Xu

      @1337c0d3r:
      how about build a complete tree of height 1, then build bigger parent and bigger sibling if enough nodes in list. So we have a complete tree of height 2, and do it recursively. the most unbalanced one is a root with a complete tree as left child and NULL as right child. Still balanced.

      VN:F [1.9.22_1171]
      0
      1. hpPlayer

        Bro, I don’t know if you can still see this, but the problem requires a height balanced BST. Your output is not balanced

        VA:F [1.9.22_1171]
        0
  7. 1337c0d3r

    @abayley:
    The list parameter is required to be passed as reference, as its pointer is changed as we traverse the list. If you couldn't use reference in a language, maybe a simple global variable will do?

    VA:F [1.9.22_1171]
    0
  8. 1337c0d3r

    @godheadatomic:
    I assume your rebalance (rotate) operation would take O(log(N)) time. Therefore, your iterative approach's run time complexity is O(N log(N)).

    VA:F [1.9.22_1171]
    0
  9. Anonymous

    @1337c0d3r
    About your response to @abayley, does the pointer have to be a reference? Since we are passing it as an argument, is it possible to just use a pointer?
    I guess I'm just confused why it has to be passed by reference.

    VA:F [1.9.22_1171]
    0
  10. Algoseekar

    @ihas1337code will create BST or Binary Tree please reply asap…i think it will create binary tree try for linked list has data values as 1 2 3 4 5..& please let mem know

    VA:F [1.9.22_1171]
    0
  11. hendry

    I think there is a bug in line 9
    parent->right = sortedListToBST(list, mid+1, end);
    mid+1 and end is right for the function input, but list is already updated at line 5 and line 8, so the index mid+1 to end is no longer right here.

    VA:F [1.9.22_1171]
    0
  12. sheen

    I may be wrong. I think the implementation is incorrect.

    list = list->next;

    We should change this statement to while loop until we meet the mid one. Otherwise, there is no point we pass in start and end. And the tree wouldn’t be balanced bst.

    Correct me if I am wrong.

    VA:F [1.9.22_1171]
    0
      1. algorist2011

        Hi can you please explain the approach above…. this is Pretty recursive in nature algorithm. And i am not getting the approach.. Please examplify!! 🙂

        VA:F [1.9.22_1171]
        0
  13. xTristan

    This approach is elegant. Great! Thanks!

    For languages without passing-by-reference arguments, this might be a bit trickier.

    Would this simpler algo work:

    Given you know the length of your list (the same assumption you are making for your algo. If not, an extra linear scan would suffice as well), create an array tree_nodes[len]. Note this is not extra space because in order to get the tree constructed you need that much space anyway.

    Start from the beginning of your list, for each list node at position i, create a tree node and place it in tree_nodes[i].

    After the entire list is scanned, you have an array converted from the linked list. From that everything is trivial.

    I admit this is actually 2N because it requires a linear visit to the tree_nodes[len] array. We may be able to get rid of this if at the first loop we can figure out the parent index and child index of each node at constant time. Any thoughts?

    pseudo code:

    VA:F [1.9.22_1171]
    +1
    1. xTristan

      the for loop above got messed up after submitting. re-attach:

      for (int i = 0; i < length; i++)
      tree_nodes[i] = new Node(head.data);
      head = head.next;
      }

      VA:F [1.9.22_1171]
      0
        1. xTristan

          Essentially yes, but not using the exact array algorithm. The first loop creates the tree nodes already, therefore, space-wise, you don’t waste any space comparing to the algorithm in this post.

          Time-complexity, yes, although both are linear, this approach requires an extra loop, which is bad. But on the other hand, recursion comes with its own price as well. Recursion requires pushing/popping on the call stack each time you recurse, which are not free operations.

          VA:F [1.9.22_1171]
          +1
  14. Pingback: NEIL

  15. Pingback: Convert a sorted doubly linked list to BST in place | NEIL

  16. wwwyhx

    Inplace makes sense
    NODE* _inner_construct(NODE* pHead, int nLen)
    {
    if (NULL == pHead || nLen <= 0)
    return NULL;

    NODE* pMid = pHead;
    for (int i = 0; i pRgt;

    pMid->pLft = _inner_construct(pHead, nLen/2);
    pMid->pRgt = _inner_construct(pMid->pRgt, nLen-1-nLen/2);

    return pMid;
    }

    VA:F [1.9.22_1171]
    -1
  17. opoopo

    Parameter start, end in 1337’s code is not necessary, we can use len instead, Java code below:

    public class Test {
    public static Node list = null;
    public static TreeNode sortedListToBST(int len) {
    if (len <= 0) return null;
    TreeNode leftChild = sortedListToBST(len/2);
    TreeNode parent = new TreeNode(list.key);
    parent.left = leftChild;
    list = list.next;
    parent.right = sortedListToBST(len-len/2-1);
    return parent;
    }
    public static TreeNode sortedListToBST(Node head, int n) {
    list = head;
    return sortedListToBST(n);
    }
    }

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

    Nice solution. However, unlike BST to Linked list solution where Binary tree nodes were used to represent a node in linked list, this solution creates new binary tree nodes. Thus O(N) space is required. i wonder if any solution exists without using extra space? One you already mentioned above, but that take O(NlogN).

    VA:F [1.9.22_1171]
    0
  19. Amit Kumar Swami

    I think there is a bug in program. the line 5 should be placed after line 8. when list is updated. Otherwise left child will add same data as root.

    VA:F [1.9.22_1171]
    0
  20. LT

    I guess the way to reconstruct a balanced BST is similar to the way of traversing a tree. This question reconstruct the tree using “in-order” traverse.
    So if we have another question like “Give a linked list, the numbers in front half size of list is increasing and in back half size of list in decreasing, convert the linked list to balanced BST”.
    Can we just simply change answer of this question to “post order” traverse?

    BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
    if (start > end) return NULL;
    // same as (start+end)/2, avoids overflow
    int mid = start + (end – start) / 2;
    BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
    BinaryTree *rightChild = sortedListToBST(list, mid+1, end);
    BinaryTree *parent = new BinaryTree(list->data);
    parent->left = leftChild;
    parent->right = rightChild;
    list = list->next;

    return parent;
    }

    BinaryTree* sortedListToBST(ListNode *head, int n) {
    return sortedListToBST(head, 0, n-1);
    }

    VN:F [1.9.22_1171]
    0
  21. Pingback: Convert Sorted List to Balanced Binary Search Tree (BST) | This is how Cheng grows up

  22. sean

    private TreeNode sortedListToBST(ref ListNode node, int start, int end)
    {
    if (start > end)
    {
    return null;
    }

    int mid = start + (end – start) >> 1;
    var l = sortedListToBST(ref node, start, mid – 1);
    var r = sortedListToBST(ref node, mid + 1, end);
    TreeNode p = new TreeNode(node.Val);
    p.LeftChild = l;
    p.RightChild = r;
    node = node.Next;
    return p;
    }

    tried this in c#, got StackOverflow.

    VA:F [1.9.22_1171]
    0
  23. Pingback: Convert Sorted Array to Binary Search Tree – ZJustin@UMich

  24. ja

    do we really need to know the length of the link list?

    We can start from head. We know it should correspond to 2^0 = 1 in bst. we know we need to stop at 2^1 link-list node, then we know we need to stop at 2^2 link list node, 2^3 and so on….

    VA:F [1.9.22_1171]
    0
  25. Punit Patel

    Here is the iterative version

    VA:F [1.9.22_1171]
    0
  26. butlerain

    void buildBST(ListNode * pn, int size){
    TreeNode * pt;
    if(size==0){
    return null;
    }else if(size == 1){
    pt->val=pn->val;
    pt->left = null;
    pt->right = null;
    return pt;
    }else {
    ListNode * p=pn;
    int middle = size/2;
    for(int i = 0; inext;
    }
    pt->val=p->val;
    pt->left = buildBST(pn, size/2);
    pt->right = buildBST(p->next, size/2-1);
    return pt;
    }
    }

    void main(){
    buildBST(head, N);
    }

    VN:F [1.9.22_1171]
    0
  27. Pingback: leetcode: Convert Sorted List to Binary Search Tree solution | 烟客旅人 sigmainfy

  28. ted cheng

    Hi, why the following code can’t pass the online judge? It’s basically the same code as in the “Best Solution” section, just in Java. Thank you for any input.

    VN:F [1.9.22_1171]
    +2
    1. Toby

      replace the line “ list = list.next;"
      with the lines below:

      if (list.next!=null) {
      list.val = list.next.val;
      list.next = list.next.next;
      }

      VA:F [1.9.22_1171]
      +1
  29. lcn

    Solution for fixing Java’s no-argument-passed-with-pointer issue: place the head of the list in an array, and this gives us a pseudo “pointer”.

    VN:F [1.9.22_1171]
    +4
  30. zach

    cool! To understand this algorithm, just remember that the function
    BinaryTree* sortedListToBST(ListNode *& list, int start, int end) actually does the following two main things:
    1. It creates a balanced BST for nodes from “start” to “end”
    2. During the process in creating the BST, it also moves the “list” pointer to point at the node after the “end” node.

    VA:F [1.9.22_1171]
    +6
  31. LK

    VA:F [1.9.22_1171]
    -1
  32. Pingback: Fun code to Convert Sorted Array to Binary Search Tree | Changhaz's Codeplay

  33. kiran

    Is the code provided for sortedListToBST correct ? anybody tested this ? I tried testing this and I get a wrong output and a wrong tree was built.

    Below is the code that i used.


    #include
    #include

    typedef struct single_link_list {
    int i;
    struct single_link_list *next;
    } slist;

    typedef struct binarytree {
    int i;
    struct binarytree *left;
    struct binarytree *right;
    } bst;

    addelemt(slist **sl, int i)
    {
    slist *tmp;

    if (*sl == NULL)
    {
    *sl = malloc(sizeof(slist *));
    (*sl)->i = i;
    (*sl)->next = NULL;
    } else {
    tmp = malloc(sizeof(slist *));
    tmp->i = i;
    tmp->next = *sl;
    *sl = tmp;
    }
    }

    printlist(slist *sl)
    {
    slist *tmp;
    tmp = sl;
    printf("\n printing the list\n");
    while (tmp != NULL)
    {
    printf("%d ", tmp->i);
    tmp = tmp->next;
    }
    }

    bst* sortedListToBST(slist *list, int start, int end) {
    printf("\n Entered for %d", list->i);

    if (start > end) return NULL;

    // same as (start+end)/2, avoids overflow
    int mid = start + (end - start) / 2;

    bst *leftChild = sortedListToBST(list, start, mid-1);
    bst *parent = malloc(sizeof(bst));
    parent->i = list->i;
    printf("\n creating root for %d", list->i);
    parent->left = leftChild;
    list = list->next;
    parent->right = sortedListToBST(list, mid+1, end);
    return parent;
    }

    preorder_printtree(bst *tree)
    {
    if (tree != NULL) {
    printf(" %d", tree->i);
    preorder_printtree(tree->left);
    preorder_printtree(tree->right);
    }
    return;
    }

    inorder_printtree(bst *tree)
    {
    if (tree != NULL) {
    inorder_printtree(tree->left);
    printf(" %d ", tree->i);
    inorder_printtree(tree->right);
    }
    return;
    }

    main()
    {
    slist *list1 = NULL;
    slist *list2 = NULL;
    int carry = 0;
    bst *tree;

    //addelemt(&list1, 9);
    addelemt(&list1, 8);
    addelemt(&list1, 7);
    addelemt(&list1, 6);
    addelemt(&list1, 5);
    addelemt(&list1, 4);
    addelemt(&list1, 3);
    addelemt(&list1, 2);
    addelemt(&list1, 1);
    printlist(list1);

    tree = sortedListToBST(list1, 0, 7);
    //preorder_printtree(tree);
    inorder_printtree(tree);

    }

    expeted output: 1 2 3 4 5 6 7 8
    actual output: 3 2 3 1 3 2 3 4

    VA:F [1.9.22_1171]
    0
  34. Pingback: DS conversion | GO 2 Computer Science and Trading Technologies

  35. networkguy88

    Since you’re traversing the whole list to find the length, what if you created a hash that mapped a nodes place in the list to the node itself (also requiring N work)? In this example:

    hash[0] = 12’s node object
    hash[1] = 99’s node object
    hash[2] = 33’s node object

    The hash would allow you to re-use your sorted array to balanced BST algorithm.

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

  37. Pingback: [LeetCode] Convert Sorted List to Binary Search Tree, Solution | 水中的鱼(镜像)

  38. Xiaohui Liu

    A slightly improved implementation, hopeful it’s easier to grasp.

    VA:F [1.9.22_1171]
    0
  39. Pingback: Leetcode - Convert Sorted List to Binary Search Tree - Timshel

  40. Pingback: Convert Sorted List to Binary Search Tree | Wenxiang's Evolutionary World

  41. Pingback: Convert Sorted List to Binary Search Tree | dev4future

  42. Pingback: [LeetCode] Convert Sorted List to Binary Search Tree | thorcsblog

  43. Pingback: Convert Sorted List to Binary Search Tree-IT技术

Leave a Reply

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

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

*