Problem description:

Given a Doubly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion)

Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Input:  Doubly Linked List 1  2  3
Output: A Balanced BST 
     2   
   /  \  
  1    3 


Input: Doubly Linked List 1  2 3  4 5  6  7
Output: A Balanced BST
        4
      /   \
     2     6
   /  \   / \
  1   3  4   7  

Input: Doubly Linked List 1  2  3  4
Output: A Balanced BST
      3   
    /  \  
   2    4 
 / 
1

Input:  Doubly Linked List 1  2  3  4  5  6
Output: A Balanced BST
      4   
    /   \  
   2     6 
 /  \   / 
1   3  5

Solution:

  • Naive solution:

    1
    2
    3
    4
    5
    6
    1) Get the Middle of the linked list and make it root.
    2) Recursively do same for left half and right half.
           a) Get the middle of left half and make it left child of the root
              created in step 1.
           b) Get the middle of right half and make it right child of the
              root created in step 1.

  • Better run time solution:
    Construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Doubly Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we assign middle node to root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
    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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* A Doubly Linked List node that will also be used as a tree node */
struct Node
{
    int data; 
    // For tree, next pointer can be used as right subtree pointer
    struct Node* next;
    // For tree, prev pointer can be used as left subtree pointer
    struct Node* prev;
};
 
//to count nodes in a Linked List, so we can know when is half
int countNodes(struct Node *head)
{
    int count = 0;
    struct Node *temp = head;
    while(temp)
    {
        temp = temp->next;
        count++;
    }
    return count;
}
 
struct Node* sortedListToBSTRecur(struct Node **head_ref, int n);
 
struct Node* sortedListToBST(struct Node *head)
{
    int n = countNodes(head);
    return sortedListToBSTRecur(&head, n);
}
 
/* The main function that constructs balanced BST and returns root of it.
       head_ref -->  Pointer to pointer to head node of Doubly linked list
       n  --> No. of nodes in the Doubly Linked List */
struct Node* sortedListToBSTRecur(struct Node **head_ref, int n)
{
    /* Base Case */
    if (n <= 0)
        return NULL;
 
    /* Recursively construct the left subtree */
    struct Node *left = sortedListToBSTRecur(head_ref, n/2);
 
    /* head_ref now refers to middle node, make middle node as root of BST*/
    struct Node *root = *head_ref;
 
    // Set pointer to left subtree
    root->prev = left;
 
    /* Change head pointer of Linked List for parent recursive calls */
    *head_ref = (*head_ref)->next;
 
    /* Recursively construct the right subtree and link it with root
      The number of nodes in right subtree  is total nodes - nodes in
      left subtree - 1 (for root) */
    root->next = sortedListToBSTRecur(head_ref, n-n/2-1);
 
    return root;
}

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/jEcKjy