Convert Sorted Linked list to balanced BST

In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list.

Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1).

Approach :
i. Get the middle of the linked list and make the middle element as root of the tree.
ii. Recursively do the same for left and right half of linked list.

struct list
{
    int value;
    struct list* next;
};

struct node
{
    int value;
    struct node* left;
    struct node* right;
};

struct node* newNode(int value);
int countNodes(struct list *head);
struct node* linkedListToBSTUtil(struct list **head, int begin,int end);

int countNodes(struct list *head)
{
  int count = 0;
  while(head!=NULL)
  {
    count++;
    head=head->next;
  }
  return count;  
}

struct node* newNode(int value)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->value = value;
    newnode->left = NULL;
    newnode->right = NULL;
  
    return newnode;
}
struct node* linkedListToBST(struct list *head)
{
    int n = countNodes(head);
    return linkedListToBSTUtil(&head, 0,n-1);
}

struct node* linkedListToBSTUtil(struct list **head, int start,int end)
{
    if (start > end)
        return NULL;
    
    int mid = start+(end-start)/2;
    struct list * temp = *head;
    int i = 0;
    while(i<mid && temp->next!=NULL)
    {
        temp = temp->next;
        i++;
    }
    struct node *root = newNode(temp->value);
    root->left = linkedListToBSTUtil(head, start, mid-1);
    root->right = linkedListToBSTUtil(head, mid+1, end);
    return root;
}

Time Complexity : O(NlogN)

Better Solution (bottom -up manner) : In this approach,We create the tree from bottom to root. This enables us to insert nodes in the tree in the same order as they appear in the list. So we don’t need to find the middle element as we are able to traverse list while inserting nodes to the tree. We first count the total number of nodes in the list.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). While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.

struct node* linkedListToBST(struct list *head)
{
    int n = countNodes(head);
    return linkedListToBSTUtil(&head, 0,n-1);
}

struct node* linkedListToBSTUtil(struct list **head, int start,int end)
{
    if (start > end)
        return NULL;
    
    int mid = start+(end-start)/2;

    struct node *leftChild = linkedListToBSTUtil(head,start,mid-1);

    struct node *root = newNode((*head)->value);
    root->left = leftChild;
    *head = (*head)->next;
    
    root->right = linkedListToBSTUtil(head, mid+1,end);
    
    return root;
}

3 Thoughts on “Convert Sorted Linked list to balanced BST

  1. I think the 2nd approach won’t give the expected output.Below is my observation:
    The head remain same for all the recursive call for left child hence the root of the tree would be the first node of the linked list instead of the mid node of the list.
    E.g 2->4->6->8->10->12->14
    The root of the tree would be 2 and left would also be 2.

  2. 1st approach also wouldn’t work while constructing right subtree.
    You should pass temp->next instead of head during below call.
    root->right = linkedListToBSTUtil(head, mid+1, end);
    There is no need to use ** as we are not modifying list.

    • Raghvendra Mishra on June 14, 2016 at 6:08 pm said:

      Replacing root->right = linkedListToBSTUtil(head, mid+1,end);
      withroot->right = linkedListToBSTUtil(temp->next, mid+1,end); should work

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation