fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* A Doubly Linked List node that
  5. will also be used as a tree node */
  6. class Node 
  7. { 
  8. 	public:
  9. 	int data; 
  10.  
  11. 	// For tree, next pointer can be
  12. 	// used as right subtree pointer 
  13. 	Node* next; 
  14.  
  15. 	// For tree, prev pointer can be
  16. 	// used as left subtree pointer 
  17. 	Node* prev; 
  18. }; 
  19.  
  20. // A utility function to count nodes in a Linked List 
  21. int countNodes(Node *head); 
  22.  
  23. Node* sortedListToBSTRecur(Node **head_ref, int n); 
  24.  
  25. /* This function counts the number of 
  26. nodes in Linked List and then calls 
  27. sortedListToBSTRecur() to construct BST */
  28. Node* sortedListToBST(Node *head) 
  29. { 
  30. 	/*Count the number of nodes in Linked List */
  31. 	int n = countNodes(head); 
  32.  
  33. 	/* Construct BST */
  34. 	return sortedListToBSTRecur(&head, n); 
  35. } 
  36.  
  37. /* The main function that constructs 
  38. balanced BST and returns root of it. 
  39. head_ref --> Pointer to pointer to
  40. head node of Doubly linked list 
  41. n --> No. of nodes in the Doubly Linked List */
  42. Node* sortedListToBSTRecur(Node **head_ref, int n) 
  43. { 
  44. 	/* Base Case */
  45. 	if (n <= 0) 
  46. 		return NULL; 
  47.  
  48. 	/* Recursively construct the left subtree */
  49. 	Node *left = sortedListToBSTRecur(head_ref, n/2); 
  50.  
  51. 	/* head_ref now refers to middle node,
  52. 	make middle node as root of BST*/
  53. 	Node *root = *head_ref; 
  54.  
  55. 	// Set pointer to left subtree 
  56. 	root->prev = left; 
  57.  
  58. 	/* Change head pointer of Linked List
  59. 	for parent recursive calls */
  60. 	*head_ref = (*head_ref)->next; 
  61.  
  62. 	/* Recursively construct the right 
  63. 	subtree and link it with root 
  64. 	The number of nodes in right subtree
  65. 	is total nodes - nodes in 
  66. 	left subtree - 1 (for root) */
  67. 	root->next = sortedListToBSTRecur(head_ref, n-n/2-1); 
  68.  
  69. 	return root; 
  70. } 
  71.  
  72. /* UTILITY FUNCTIONS */
  73. /* A utility function that returns 
  74. count of nodes in a given Linked List */
  75. int countNodes(Node *head) 
  76. { 
  77. 	int count = 0; 
  78. 	Node *temp = head; 
  79. 	while(temp) 
  80. 	{ 
  81. 		temp = temp->next; 
  82. 		count++; 
  83. 	} 
  84. 	return count; 
  85. } 
  86.  
  87. /* Function to insert a node at 
  88. the beginning of the Doubly Linked List */
  89. void push(Node** head_ref, int new_data) 
  90. { 
  91. 	/* allocate node */
  92. 	Node* new_node = new Node();
  93.  
  94. 	/* put in the data */
  95. 	new_node->data = new_data; 
  96.  
  97. 	/* since we are adding at the beginning, 
  98. 	prev is always NULL */
  99. 	new_node->prev = NULL; 
  100.  
  101. 	/* link the old list of the new node */
  102. 	new_node->next = (*head_ref); 
  103.  
  104. 	/* change prev of head node to new node */
  105. 	if((*head_ref) != NULL) 
  106. 	(*head_ref)->prev = new_node ; 
  107.  
  108. 	/* move the head to point to the new node */
  109. 	(*head_ref) = new_node; 
  110. } 
  111.  
  112. /* Function to print nodes in a given linked list */
  113. void printList(Node *node) 
  114. { 
  115. 	while (node!=NULL) 
  116. 	{ 
  117. 		cout<<node->data<<" "; 
  118. 		node = node->next; 
  119. 	} 
  120. } 
  121.  
  122. /* A utility function to print
  123. preorder traversal of BST */
  124. void preOrder(Node* node) 
  125. { 
  126. 	if (node == NULL) 
  127. 		return; 
  128. 	cout<<node->data<<" "; 
  129. 	preOrder(node->prev); 
  130. 	preOrder(node->next); 
  131. } 
  132.  
  133. /* Driver code*/
  134. int main() 
  135. { 
  136. 	/* Start with the empty list */
  137. 	Node* head = NULL; 
  138.  
  139. 	/* Let us create a sorted linked list to test the functions 
  140. 	Created linked list will be 7->6->5->4->3->2->1 */
  141. 	push(&head, 7); 
  142. 	push(&head, 6); 
  143. 	push(&head, 5); 
  144. 	push(&head, 4); 
  145. 	push(&head, 3); 
  146. 	push(&head, 2); 
  147. 	push(&head, 1); 
  148.  
  149. 	cout<<"Given Linked List\n"; 
  150. 	printList(head); 
  151.  
  152. 	/* Convert List to BST */
  153. 	Node *root = sortedListToBST(head); 
  154. 	cout<<"\nPreOrder Traversal of constructed BST \n "; 
  155. 	preOrder(root); 
  156.  
  157. 	return 0; 
  158. } 
  159.  
  160. // This code is contributed by rathbhupendra
  161.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Given Linked List
1 2 3 4 5 6 7 
PreOrder Traversal of constructed BST 
 4 2 1 3 6 5 7
https://ideone.com/baWiLo
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!