C Programming Code Examples C > Linked Lists Code Examples Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List This C Program creates a balanced binary search tree which has same data members as the given Doubly linked list by changing the pointers internally. #include <stdio.h> #include <stdlib.h> struct node { int x; struct node *left; struct node *right; }; void create(struct node **); void treemaker(struct node **, int); void display(struct node *); void displayTree(struct node *); void delete(struct node **); int main() { struct node *headList = NULL, *rootTree, *p; int count = 1, flag = 0; create(&headList); printf("Displaying the doubly linked list:\n"); display(headList); rootTree = p = headList; while (p->right != NULL) { p = p->right; count = count + 1; if (flag) { rootTree = rootTree->right; } flag = !flag; } treemaker(&rootTree, count / 2); printf("Displaying the tree: (Inorder)\n"); displayTree(rootTree); printf("\n"); return 0; } void create(struct node **head) { struct node *rear, *temp; int a, ch; do { printf("Enter a number: "); scanf("%d", &a); temp = (struct node *)malloc(sizeof(struct node)); temp->x = a; temp->right = NULL; temp->left = NULL; if (*head == NULL) { *head = temp; } else { rear->right = temp; temp->left = rear; } rear = temp; printf("Do you wish to continue [1/0] ?: "); scanf("%d", &ch); } while (ch != 0); } void treemaker(struct node **root, int count) { struct node *quarter, *thirdquarter; int n = count, i = 0; if ((*root)->left != NULL) { quarter = (*root)->left; for (i = 1; (i < count / 2) && (quarter->left != NULL); i++) { quarter = quarter->left; } (*root)->left->right = NULL; (*root)->left = quarter; /* * Uncomment the following line to see when the pointer changes */ //printf("%d's left child is now %d\n", (*root)->x, quarter->x); if (quarter != NULL) { treemaker(&quarter, count / 2); } } if ((*root)->right != NULL) { thirdquarter = (*root)->right; for (i = 1; (i < count / 2) && (thirdquarter->right != NULL); i++) { thirdquarter = thirdquarter->right; } (*root)->right->left = NULL; (*root)->right = thirdquarter; /* * Uncomment the following line to see when the pointer changes */ //printf("%d's right child is now %d\n", (*root)->x, thirdquarter->x); if (thirdquarter != NULL) { treemaker(&thirdquarter, count / 2); } } } void display(struct node *head) { while (head != NULL) { printf("%d ", head->x); head = head->right; } printf("\n"); } /*DisplayTree performs inorder traversal*/ void displayTree(struct node *root) { if (root != NULL) { displayTree(root->left); printf("%d ", root->x); displayTree(root->right); } } void delete(struct node **root) { if (*root != NULL) { displayTree((*root)->left); displayTree((*root)->right); free(*root); } }