C++ Program to Implement Sorted Linked List to Balanced BST

«
»
This C++ Program demonstrates the implementation of Sorted Linked List to Balanced BST.

Here is source code of the C++ Program to demonstrate the implementation of Sorted Linked List to Balanced BST. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Implement Sorted Linked List into Balanced BST 
  3.  */
  4. #include<iostream>
  5. #include<cstdlib>
  6. using namespace std;
  7.  
  8. /* 
  9.  * Link list node 
  10.  */
  11. struct LNode
  12. {
  13.     int data;
  14.     LNode* next;
  15. };
  16.  
  17. /* 
  18.  * A Binary Tree node 
  19.  */
  20. struct TNode
  21. {
  22.     int data;
  23.     TNode* left;
  24.     TNode* right;
  25. };
  26.  
  27.  
  28. TNode* newNode(int data);
  29. int countLNodes(LNode *head);
  30. TNode* sortedListToBSTRecur(LNode **head_ref, int n);
  31.  
  32.  
  33. /* 
  34.  * counts the number of nodes in Linked List  
  35.  */
  36. TNode* sortedListToBST(LNode *head)
  37. {
  38.     int n = countLNodes(head);
  39.     return sortedListToBSTRecur(&head, n);
  40. }
  41.  
  42. /* 
  43.  * constructs balanced BST and returns root of it. 
  44.  */
  45. TNode* sortedListToBSTRecur(LNode **head_ref, int n)
  46. {
  47.     if (n <= 0)
  48.         return NULL;
  49.     TNode *left = sortedListToBSTRecur(head_ref, n / 2);
  50.     TNode *root = newNode((*head_ref)->data);
  51.     root->left = left;
  52.     *head_ref = (*head_ref)->next;
  53.     root->right = sortedListToBSTRecur(head_ref, n - n / 2 - 1);
  54.     return root;
  55. }
  56.  
  57. /* 
  58.  * returns count of nodes in a given Linked List 
  59.  */
  60. int countLNodes(LNode *head)
  61. {
  62.     int count = 0;
  63.     LNode *temp = head;
  64.     while (temp)
  65.     {
  66.         temp = temp->next;
  67.         count++;
  68.     }
  69.     return count;
  70. }
  71.  
  72. /* 
  73.  * insert a node at the beginging of the linked list 
  74.  */
  75. void push(LNode** head_ref, int new_data)
  76. {
  77.     LNode* new_node = new LNode;
  78.     new_node->data = new_data;
  79.     new_node->next = (*head_ref);
  80.     (*head_ref) = new_node;
  81. }
  82.  
  83. /* 
  84.  * print nodes in a given linked list
  85.  */
  86. void printList(LNode *node)
  87. {
  88.     while (node != NULL)
  89.     {
  90.         cout<<node->data<<"  ";
  91.         node = node->next;
  92.     }
  93. }
  94.  
  95. /* 
  96.  * allocates a new node with the data and NULL left and right pointers.
  97.  */
  98. TNode* newNode(int data)
  99. {
  100.     TNode* node = new TNode;
  101.     node->data = data;
  102.     node->left = NULL;
  103.     node->right = NULL;
  104.     return node;
  105. }
  106.  
  107. /* 
  108.  * print preorder traversal of BST
  109.  */
  110. void preOrder(TNode* node)
  111. {
  112.     if (node == NULL)
  113.         return;
  114.     cout<<node->data<<"  ";
  115.     preOrder(node->left);
  116.     preOrder(node->right);
  117. }
  118.  
  119. /* 
  120.  * Main
  121.  */
  122. int main()
  123. {
  124.     LNode* head = NULL;
  125.     push(&head, 7);
  126.     push(&head, 6);
  127.     push(&head, 5);
  128.     push(&head, 4);
  129.     push(&head, 3);
  130.     push(&head, 2);
  131.     push(&head, 1);
  132.     cout<<"\n Given Linked List ";
  133.     printList(head);
  134.     TNode *root = sortedListToBST(head);
  135.     cout<<"\n PreOrder Traversal of constructed BST ";
  136.     preOrder(root);
  137.     return 0;
  138. }

advertisement
$ g++ sorted_bst.cpp
$ a.out
 
 Given Linked List 1  2  3  4  5  6  7
 PreOrder Traversal of constructed BST 4  2  1  3  6  5  7
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn