﻿ C Program: Binary Tree level-order traversal

# C Program: Binary Tree level-order traversal

## C Program to implement Tree Structure: Exercise-7 with Solution

Write a C program that extends the binary tree program to perform a level-order traversal. Print the nodes at each level from top to bottom.

Sample Solution:

C Code:

``````// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

// Function to create a new node
struct TreeNode* createNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode != NULL) {
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}

// Function to insert a node into the binary tree
struct TreeNode* insertNode(struct TreeNode* root, int value) {
if (root == NULL) {
return createNode(value);
}

if (value < root->data) {
root->left = insertNode(root->left, value);
} else if (value > root->data) {
root->right = insertNode(root->right, value);
}

return root;
}

// Function to perform in-order traversal and print elements in sorted order
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

// Function to perform level-order traversal and print nodes at each level
void levelOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
printf("The tree is empty.\n");
return;
}

// Create a queue for level-order traversal
struct TreeNode* queue[1000];
int front = -1, rear = -1;

// Enqueue the root node
queue[++rear] = root;

while (front != rear) {
// Dequeue a node and print its value
struct TreeNode* current = queue[++front];
printf("%d ", current->data);

// Enqueue the left child if exists
if (current->left != NULL) {
queue[++rear] = current->left;
}

// Enqueue the right child if exists
if (current->right != NULL) {
queue[++rear] = current->right;
}
}

printf("\n");
}

// Function to free the memory allocated for the binary tree
void freeTree(struct TreeNode* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}

int main() {
struct TreeNode* root = NULL;
int nodeValue;
char choice;

// Insert nodes into the binary tree
do {
printf("Input a value to insert into the binary tree (enter 0 to stop): ");
scanf("%d", &nodeValue);

if (nodeValue != 0) {
root = insertNode(root, nodeValue);
}

} while (nodeValue != 0);

// Perform in-order traversal and print elements in sorted order
printf("\nIn-order Traversal (Sorted Order) of the Binary Tree: ");
inOrderTraversal(root);
printf("\n");

// Perform level-order traversal and print nodes at each level
printf("\nLevel-order Traversal of the Binary Tree:\n");
levelOrderTraversal(root);

// Free allocated memory
freeTree(root);

return 0;
}
```
```

Output:

```Input a value to insert into the binary tree (enter 0 to stop): 78
Input a value to insert into the binary tree (enter 0 to stop): 52
Input a value to insert into the binary tree (enter 0 to stop): 48
Input a value to insert into the binary tree (enter 0 to stop): 28
Input a value to insert into the binary tree (enter 0 to stop): 22
Input a value to insert into the binary tree (enter 0 to stop): 8
Input a value to insert into the binary tree (enter 0 to stop): 6
Input a value to insert into the binary tree (enter 0 to stop): 0

In-order Traversal (Sorted Order) of the Binary Tree: 6 8 22 28 48 52 78

Level-order Traversal of the Binary Tree:
78 52 48 28 22 8 6
```

Explanation:

In the exercise above,

• Struct Definition:
• Defines a structure struct TreeNode representing a node in a binary tree. Each node has an integer data, a pointer to the left child (left), and a pointer to the right child (right).
• Function to Create a Node:
• createNode function allocates memory for a new node, initializes its data, and sets both left and right pointers to 'NULL'.
• Function to Insert a Node:
• insertNode function inserts a node into the binary tree while maintaining the binary search tree property. It recursively compares the value to be inserted with the current node's value and traverses left or right accordingly.
• In-Order Traversal Function:
• inOrderTraversal performs an in-order traversal of the binary tree, printing the elements in sorted order.
• Level-Order Traversal Function:
• levelOrderTraversal performs a level-order traversal of the binary tree. It uses a queue to keep track of nodes at each level and prints them from top to bottom.
• Free Tree Function:
• freeTree recursively frees the memory allocated for the binary tree nodes.
• Main Function:
• The main function creates an empty binary tree and allows users to input values to insert into the tree. It stops when the user enters 0. Afterward, it prints the in-order traversal (sorted order) and the level-order traversal of the binary tree.

Flowchart:

C Programming Code Editor:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿