Sorted Linked List to Balanced BST in C++

«
»
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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.