In this program, we are going to share how to sort linked list to balanced BST. If you are a beginner and want to start learning the C programming, then keep your close attention in this tutorial as I am going to share how to sort linked list to balanced BST with the output.
We have designed this program for beginners for learning purpose. Copy below c program and execute it with c compiler to see the output of the program.
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | #include<stdio.h> #include<stdlib.h> /* Link list node */ struct LNode { int data; struct LNode* next; }; /* A Binary Tree node */ struct TNode { int data; struct TNode* left; struct TNode* right; }; struct TNode* newNode(int data); int countLNodes(struct LNode *head); struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n); /* This function counts the number of nodes in Linked List and then calls sortedListToBSTRecur() to construct BST */ struct TNode* sortedListToBST(struct LNode *head) { /*Count the number of nodes in Linked List */ int n = countLNodes(head); /* Construct BST */ 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 linked list n --> No. of nodes in Linked List */ struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n) { /* Base Case */ if (n <= 0) return NULL; /* Recursively construct the left subtree */ struct TNode *left = sortedListToBSTRecur(head_ref, n/2); /* Allocate memory for root, and link the above constructed left subtree with root */ struct TNode *root = newNode((*head_ref)->data); root->left = 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) which is n-n/2-1*/ root->right = sortedListToBSTRecur(head_ref, n-n/2-1); return root; } int countLNodes(struct LNode *head) { int count = 0; struct LNode *temp = head; while(temp) { temp = temp->next; count++; } return count; } /* Function to insert a node at the beginging of the linked list */ void push(struct LNode** head_ref, int new_data) { /* allocate node */ struct LNode* new_node = (struct LNode*) malloc(sizeof(struct LNode)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct LNode *node) { while(node!=NULL) { printf("%d ", node->data); node = node->next; } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct TNode* newNode(int data) { struct TNode* node = (struct TNode*) malloc(sizeof(struct TNode)); node->data = data; node->left = NULL; node->right = NULL; return node; } /* A utility function to print preorder traversal of BST */ void preOrder(struct TNode* node) { if (node == NULL) return; printf("%d ", node->data); preOrder(node->left); preOrder(node->right); } /* Drier program to test above functions*/ int main() { /* Start with the empty list */ struct LNode* head = NULL; /* Let us create a sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6->7 */ push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf("\n Given Linked List "); printList(head); struct TNode *root = sortedListToBST(head); printf("\n PreOrder Traversal of constructed BST "); preOrder(root); return 0; } |
Given Linked List 1 2 3 4 5 6 7
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
