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;
}
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.
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.
Replacing root->right = linkedListToBSTUtil(head, mid+1,end);
withroot->right = linkedListToBSTUtil(temp->next, mid+1,end); should work
struct node *linkedlisttoBST(struct list *&head) {
list *t = head;
node *leftsubtree = NULL;
while (t) {
node *nnode = new node(t->val);
t->left = leftsubtree;
t = t->next;
if (t) {
node *rt = new node(t->val);
t->right = rt;
}
leftsubtree = t;
t = t->next;
}
return leftsubtree;
}
Complexity: O(n) no count or additional space is needed to be kept
struct node *linkedlisttoBST(struct list *&head) {
list *t = head;
node *leftsubtree = NULL;
while (t) {
node *nnode = new node(t->val);
nnode->left = leftsubtree;
t = t->next;
if (t) {
node *rt = new node(t->val);
nnode->right = rt;
}
leftsubtree = nnode;
t = t->next;
}
return leftsubtree;
}
Complexity: O(n) no count or additional space is needed to be kept
If you relax the notion of balanced to height-balanced (AVL) or red-black, there are online (one pass) algorithms that have amortized constant time per element added, with an additional finishing time O(log n), where n is the number of elements in the tree.
This is much stronger than just O(n) offline.
For red-black tree construction, see the SML/NJ implementation of sets.
For AVL trees, the per element cost can be reduced to worst-case constant time per element. I don’t know whether this is is possible for red-black trees.