C Program to Traverse Binary Tree using Recursion

Recursion : :

• Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

• The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.

• Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.

Problem : :

The following C program, using recursion, performs traversal operation across the nodes in a tree. The tree we have used is the binary search tree. The user generates a tree by inserting integers. The user is also asked to select one of the three modes of traversal, ie, infix, prefix and postfix.

Here is the source code of the C Program to Traverse Binary Tree using Recursion. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

SOURCE CODE : 

/*  C Program to Traverse Binary Tree using Recursion  */

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
    int a;
    struct node *left;
    struct node *right;
};
 
void generate(struct node **, int);
void infix(struct node *);
void postfix(struct node *);
void prefix(struct node *);
void delete(struct node **);
 
int main()
{
    struct node *head = NULL;
    int choice = 0, num, flag = 0, key;
 
    do
    {
        printf("\nEnter your choice:\n1. Insert\n2. Traverse via infix\n3.Traverse via prefix\n4. Traverse via postfix\n5. Exit\nChoice: ");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1: 
            printf("Enter element to insert: ");
            scanf("%d", &num);
            generate(&head, num);
            break;
        case 2: 
            infix(head);
            break;
        case 3: 
            prefix(head);
            break;
        case 4: 
            postfix(head);
            break;
        case 5: 
            delete(&head);
            printf("Memory Cleared\nPROGRAM TERMINATED\n");
            break;
        default: printf("Not a valid input, try again\n");
        }
    } while (choice != 5);
    return 0;
}
 
void generate(struct node **head, int num)
{
    struct node *temp = *head, *prev = *head;
 
    if (*head == NULL)
    {
        *head = (struct node *)malloc(sizeof(struct node));
        (*head)->a = num;
        (*head)->left = (*head)->right = NULL;
    }
    else
    {
        while (temp != NULL)
        {
            if (num > temp->a)
            {
                prev = temp;
                temp = temp->right;
            }
            else
            {
                prev = temp;
                temp = temp->left;
            }
        }
        temp = (struct node *)malloc(sizeof(struct node));
        temp->a = num;
        if (num >= prev->a)
        {
            prev->right = temp;
        }
        else
        {
            prev->left = temp;
        }
    }
}
 
void infix(struct node *head)
{
    if (head)
    {
        infix(head->left);
        printf("%d   ", head->a);
        infix(head->right);
    }
}
 
void prefix(struct node *head)
{
    if (head)
    {
        printf("%d   ", head->a);
        prefix(head->left);
        prefix(head->right);
    }
}
 
void postfix(struct node *head)
{
    if (head)
    {
        postfix(head->left);
        postfix(head->right);
        printf("%d   ", head->a);
    }
}
 
void delete(struct node **head)
{
    if (*head != NULL)
    {
        if ((*head)->left)
        {
            delete(&(*head)->left);
        }
        if ((*head)->right)
        {
            delete(&(*head)->right);
        }
        free(*head);
    }
}

Output : :

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 1
Enter element to insert: 5
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 1
Enter element to insert: 3
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 1
Enter element to insert: 4
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 1
Enter element to insert: 6
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 2
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 2
2   3   4   5   6  
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 3
5   3   2   4   6   

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 4
2   4   3   6   5  
 
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit

Choice: 5

Above is the source code for C Program to Traverse Binary Tree using Recursion which is successfully compiled and run on Windows System.The Output of the program is shown above .