level_order_traversal.c

trees Implementation

61 lines
1381 bytes
C
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