C Program: In-order traversal of Binary Tree for sorted elements

Last update on December 20 2024 13:09:35 (UTC/GMT +8 hours)

Write a C program to perform an in-order traversal of a binary tree. Print the elements in sorted order.

Sample Solution:

C Code:

// Including necessary header files
#include <stdio.h>
#include <stdlib.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 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");

    // Free allocated memory
    freeTree(root);

    return 0;
}

Output:

Input a value to insert into the binary tree (enter 0 to stop): 75
Input a value to insert into the binary tree (enter 0 to stop): 18
Input a value to insert into the binary tree (enter 0 to stop): 63
Input a value to insert into the binary tree (enter 0 to stop): 12
Input a value to insert into the binary tree (enter 0 to stop): 15
Input a value to insert into the binary tree (enter 0 to stop): 55
Input a value to insert into the binary tree (enter 0 to stop): 80
Input a value to insert into the binary tree (enter 0 to stop): 0

In-order Traversal (Sorted Order) of the Binary Tree: 12 15 18 55 63 75 80

Explanation:

In the exercise above,

Header Files:

The program includes necessary header files (stdio.h for input/output functions and stdlib.h for memory allocation).

TreeNode Structure:

Defines a structure "TreeNode" representing a node in a binary tree with integer data, a pointer to the left child, and a pointer to the right child.

createNode Function:

Creates a new tree node with the given integer value and returns a pointer to it.

insertNode Function:

Inserts a new node with a given value into the binary tree.
Uses recursion to find the appropriate position based on the comparison of values.

inOrderTraversal Function:

Performs in-order traversal of the binary tree and prints the elements.
Prints elements in ascending order due to in-order traversal.

freeTree Function:

Frees the memory allocated for the binary tree nodes using recursive post-order traversal.

main Function:

Initializes the root of the binary tree as 'NULL'.
Accepts user input to insert nodes into the binary tree until the user enters 0.
Performs in-order traversal and prints the elements in sorted order.
Frees the memory allocated for the binary tree.

User Interaction:

Users input values to insert into the binary tree.
The program builds the binary tree accordingly.
The in-order traversal displays the elements in sorted order.

Memory Management:

Proper memory allocation and deallocation are handled using malloc and free to avoid memory leaks.

Flowchart:

C Programming Code Editor:

Previous: C Program: Binary Tree creation with user input.
Next: C Program: Binary search Tree insertion with sorted in-order traversal.