level_order_traversal.c
trees Implementation
61 lines1381 bytesC
1// Binary Tree - Level Order Traversal (BFS)
2#include <stdio.h>
3#include <stdlib.h>
4
5struct Node {
6 int data;
7 struct Node* left;
8 struct Node* right;
9};
10
11struct Node* createNode(int data) {
12 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
13 newNode->data = data;
14 newNode->left = NULL;
15 newNode->right = NULL;
16 return newNode;
17}
18
19int height(struct Node* node) {
20 if (node == NULL) return 0;
21
22 int leftHeight = height(node->left);
23 int rightHeight = height(node->right);
24
25 return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
26}
27
28void printLevel(struct Node* root, int level) {
29 if (root == NULL) return;
30
31 if (level == 1) {
32 printf("%d ", root->data);
33 } else if (level > 1) {
34 printLevel(root->left, level - 1);
35 printLevel(root->right, level - 1);
36 }
37}
38
39void levelOrder(struct Node* root) {
40 int h = height(root);
41 for (int i = 1; i <= h; i++) {
42 printLevel(root, i);
43 }
44}
45
46int main() {
47 struct Node* root = createNode(1);
48 root->left = createNode(2);
49 root->right = createNode(3);
50 root->left->left = createNode(4);
51 root->left->right = createNode(5);
52 root->right->left = createNode(6);
53 root->right->right = createNode(7);
54
55 printf("Level Order Traversal: ");
56 levelOrder(root);
57 printf("\n");
58
59 return 0;
60}
61