C Program for Depth First Binary Tree Search without using Recursion

# C Program for Depth First Binary Tree Search without using Recursion

4347
0
SHARE

C Program for Depth First Binary Tree Search without using Recursion : The following performs a Depth First Search traversal. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure or graph. The concept of backtracking is used in DFS. In this program we are performing DFS on a binary tree. In DFS, the deepest and unvisited node is visited and backtracks to itâ€™s root if no siblings of that node exists.

Here is the source code of the C program to apply DFS on a binary tree:

```#include <stdio.h>

#include <stdlib.h>

struct node

{

int a;

struct node *left;

struct node *right;

int visited;

};

void generate(struct node **, int);

void DFS(struct node *);

void delete(struct node **);

int main()

{

int choice = 0, num, flag = 0, key;

do

{

printf("\nEnter your choice:\n1. Insert\n2. Perform DFS Traversal\n3. Exit\nChoice: ");

scanf("%d", &choice);

switch(choice)

{

case 1:

printf("Enter element to insert: ");

scanf("%d", &num);

break;

case 2:

break;

case 3:

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)

{

{

*head = (struct node *)malloc(sizeof(struct node));

}

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;

temp->visited = 0;

if (temp->a >= prev->a)

{

prev->right = temp;

}

else

{

prev->left = temp;

}

}

}

{

struct node *temp = head, *prev;

printf("On DFS traversal we get:\n");

while (temp && !temp->visited)

{

if (temp->left && !temp->left->visited)

{

temp = temp->left;

}

else if (temp->right && !temp->right->visited)

{

temp = temp->right;

}

else

{

printf("%d  ", temp->a);

temp->visited = 1;

}

}

}

{

{

{

}

{

}

}

}```

OUTPUT OF PROGRAM :

```Enter your choice:
1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 5

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 3

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 2

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 4

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 1

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 7

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 6

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 1
Enter element to insert: 8

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 2
On DFS traversal we get:
1  2  4  3  6  8  7  5

1. Insert
2. Perform DFS Traversal
3. Exit
Choice: 3
Memory Cleared
PROGRAM TERMINATED```

Hope this helps. In case of any queries feel free to ask.

SHARE
Previous articleC Program to Traverse the Tree without using Recursion
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