-
Notifications
You must be signed in to change notification settings - Fork 0
/
sortedListToBST.cpp
157 lines (129 loc) · 4.06 KB
/
sortedListToBST.cpp
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
149
150
151
152
153
154
155
156
157
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
/* 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)
{
cout<< "Moving to right"<<(*head_ref)->data<<endl ;
/* 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;
}
/* UTILITY FUNCTIONS */
/* A utility function that returns count of nodes in a given Linked List */
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);
/* Convert List to BST */
struct TNode *root = sortedListToBST(head);
printf("\n PreOrder Traversal of constructed BST ");
preOrder(root);
return 0;
}