Home / C Programs / C Program to Traverse the Tree without using Recursion

C Program to Traverse the Tree without using Recursion

C Program to Traverse the Tree without using Recursion : This will traverse the tree without using Recursion. The following C program, using iteration, searches for a given node in a tree. The tree we have used is the binary search tree. A binary search tree follows a concept of the nodes whose are lesser than the parent/pointed node are linked to the left and the nodes whose are greater than the parent/pointed node are linked to the right.

Here is the source code of the C program to search for an element in a tree:

#include <stdio.h>

#include <stdlib.h>

 

struct node

{

    int a;

    struct node *left;

    struct node *right;

};

 

void generate(struct node **, int);

int search(struct node *, int);

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. Search\n3. Exit\nChoice: ");

        scanf("%d", &choice);

        switch(choice)

        {

        case 1: 

            printf("Enter element to insert: ");

            scanf("%d", &num);

            generate(&head, num);

            break;

        case 2: 

            printf("Enter key to search: ");

            scanf("%d", &key);

            flag = search(head, key);

            if (flag)

            {

                printf("Key found in tree\n");

            }

            else

            {

                printf("Key not found\n");

            }

            break;

        case 3: 

            delete(&head);

            printf("Memory Cleared\nPROGRAM TERMINATED\n");

            break;

        default: printf("Not a valid input, try again\n");

        }

    } while (choice != 3);

    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;

        }

    }

}

 

int search(struct node *head, int key)

{

    while (head != NULL)

    {

        if (key > head->a)

        {

            head = head->right;

        }

        else if (key < head->a)

        {

            head = head->left;

        }

        else

        {

            return 1;

        }

    }

	return 0;

}

 

void delete(struct node **head)

{

    if (*head != NULL)

    {

        if ((*head)->left)

        {

            delete(&(*head)->left);

        }

        if ((*head)->right)

        {

            delete(&(*head)->right);

        }

        free(*head);

    }

}

 

OUTPUT OF PROGRAM :

Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 1
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 2
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 3
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 1
Enter element to insert: 
4
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 2
Enter key to search: 1
Key found in tree
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 2
Enter key to search: 6
Key not found
 
Enter your choice:
1. Insert
2. Search
3. Exit
Choice: 3
Memory Cleared
PROGRAM TERMINATED

 

Hope this helps! Let me know in case of any queries.

About Mr Coder

Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com

Check Also

C Program to solve Knapsack Problem using Greedy Algorithm

C Program to solve Knapsack Problem using Greedy Algorithm : Below you can find how …

Leave a Reply

Your email address will not be published. Required fields are marked *