# C Program to Convert Binary Tree to Singly Linked List

This C Program converts a binary tree into a singly linked list by Breadth first search algorithm. We use this algorithm for traversing level by level

Here is a source code of the C program that converts a binary tree into a singly linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C Program to Convert a Binary Tree into a Singly Linked List by Traversing Level by Level `
3. ` */`
4. `<pre>`
5. `#include <stdio.h>`
6. `#include <stdlib.h>`
7. ` `
8. `/*structure type to create a tree*/`
9. `struct node`
10. `{`
11. `    int num;`
12. `    struct node *left;`
13. `    struct node *right;`
14. `};`
15. `/*`
16. ` * structure type to point to the nodes of a tree`
17. ` * and also create self-referential list used for`
18. ` * queueing.`
19. ` */`
20. `struct queue`
21. `{`
22. `    struct node *nodeptr;`
23. `    struct queue *next;`
24. `};`
25. `/* resulting singly linked list */`
26. `struct list`
27. `{`
28. `    int num;`
29. `    struct list *next;`
30. `};`
31. ` `
32. `void createTree(struct node **);`
33. `void createlistbfs(struct node *, struct list **);`
34. `void delete(struct node **);`
35. `void display(struct list *);`
36. `void deleteList(struct list **);`
37. ` `
38. `int main()`
39. `{`
40. `    struct node *root = NULL;`
41. `    struct list *head = NULL;`
42. ` `
43. `    createTree(&root);`
44. `    createlistbfs(root, &head);`
45. `    printf("Displaying the list generated at node by node level of the tree: ");`
46. `    display(head);`
47. `    deleteList(&head);`
48. `    delete(&root);`
49. ` `
50. `    return 0;`
51. `}`
52. ` `
53. `void createTree(struct node **root)`
54. `{`
55. `    struct node *temp, *p, *q;`
56. `    int a, ch;`
57. ` `
58. `    do`
59. `    {`
60. `        printf("Enter a number for a node: ");`
61. `        scanf("%d", &a);`
62. `        temp = (struct node *)malloc(sizeof(struct node));`
63. `        temp->num = a;`
64. `        temp->left = NULL;`
65. `        temp->right = NULL;`
66. `        p = q = *root;`
67. `        if (*root == NULL)`
68. `        {`
69. `            *root = temp;`
70. `        }`
71. `        else`
72. `        {`
73. `            while (1)`
74. `            {`
75. `                q = p;`
76. `                if (p->num >= temp->num)`
77. `                {`
78. `                    p = p->left;`
79. `                }`
80. `                else`
81. `                {`
82. `                    p = p->right;`
83. `                }`
84. `                if (p == NULL)`
85. `                {`
86. `                    break;`
87. `                }`
88. `            }`
89. `            if (q->num >= temp->num)`
90. `                q->left = temp;`
91. `            else`
92. `                 q->right = temp;`
93. `        }`
94. `        printf("Do you want to continue? [1/0]: ");`
95. `        scanf("%d", &ch);`
96. `    } while (ch != 0);`
97. `}`
98. ` `
99. `void createlistbfs(struct node *root, struct list **head)`
100. `{`
101. `    struct queue *qhead, *qrear, *qtemp, *qrelease;`
102. `    struct list *temp, *rear;`
103. ` `
104. `    if (root == NULL)`
105. `    {`
106. `        return;`
107. `    }`
108. `    qhead = (struct queue *)malloc(sizeof(struct queue));`
109. `    qhead->nodeptr = root;`
110. `    qhead->next = NULL;`
111. `    qrear = qhead;`
112. `    while (qhead != NULL)`
113. `    {`
114. ` `
115. `        temp = (struct list *)malloc(sizeof(struct list));`
116. `        temp->num = qhead->nodeptr->num;`
117. `        temp->next = NULL;`
118. `        if (*head == NULL)`
119. `        {`
120. `            *head = temp;`
121. `        }`
122. `        else`
123. `        {`
124. `            rear->next = temp;`
125. `        }`
126. `        rear = temp;`
127. `        if (qhead->nodeptr->left != NULL)`
128. `        {`
129. `            qtemp = (struct queue *)malloc(sizeof(struct queue));`
130. `            qtemp->nodeptr = qhead->nodeptr->left;`
131. `            qtemp->next = NULL;`
132. `            qrear->next = qtemp;`
133. `            qrear = qtemp;`
134. `        }`
135. `        if (qhead->nodeptr->right != NULL)`
136. `        {`
137. `            qtemp = (struct queue *)malloc(sizeof(struct queue));`
138. `            qtemp->nodeptr = qhead->nodeptr->right;`
139. `            qtemp->next = NULL;`
140. `            qrear->next = qtemp;`
141. `            qrear = qtemp;`
142. `        }`
143. `        qrelease = qhead;`
144. `        qhead = qhead->next;`
145. `        free(qrelease);`
146. `    }`
147. `}`
148. ` `
149. `void delete(struct node **root)`
150. `{`
151. `    if (*root == NULL)`
152. `    {`
153. `        return;`
154. `    }`
155. `    else`
156. `    {`
157. `        if ((*root)->left != NULL)`
158. `        {`
159. `            delete(&((*root)->left));`
160. `        }`
161. `        if ((*root)->right != NULL)`
162. `        {`
163. `            delete(&((*root)->right));`
164. `        }`
165. `    }`
166. `}`
167. ` `
168. `void display(struct list *head)`
169. `{`
170. `    while (head != NULL)`
171. `    {`
172. `        printf("%d  ", head->num);`
173. `        head = head->next;`
174. `    }`
175. `}`
176. ` `
177. `void deleteList(struct list **head)`
178. `{`
179. `    struct list *temp;`
180. ` `
181. `    temp = *head;`
182. `    while (temp != NULL)`
183. `    {`
184. `        *head = (*head)->next;`
185. `        free(temp);`
186. `        temp = *head;`
187. `    }`
188. `}`

```\$ gcc treetolistbfs.c
\$ ./a.out
Enter a number for a node: 4
Do you want to continue? [1/0]: 1
Enter a number for a node: 2
Do you want to continue? [1/0]: 1
Enter a number for a node: 3
Do you want to continue? [1/0]: 1
Enter a number for a node: 1
Do you want to continue? [1/0]: 1
Enter a number for a node: 6
Do you want to continue? [1/0]: 1
Enter a number for a node: 5
Do you want to continue? [1/0]: 1
Enter a number for a node: 8
Do you want to continue? [1/0]: 1
Enter a number for a node: 7
Do you want to continue? [1/0]: 1
Enter a number for a node: 9
Do you want to continue? [1/0]: 0
Displaying the list generated at node by node level of the tree: 4  2  6  1  3  5  8  7  9```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]