ADVERTISEMENT
ADVERTISEMENT

C program to search an item in the binary tree

Here, we are going to learn how to search an item in the binary tree using C program?
Submitted by Nidhi, on August 24, 2021

Problem Solution:

Create a binary tree, and then search an item in the binary tree.

Program:

The source code to search an item in the binary tree is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to search an item in binary tree

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int item;
    struct node* left;
    struct node* right;

} Node;

void AddNode(Node** root, int item)
{
    Node* temp = *root;
    Node* prev = *root;

    if (*root == NULL) {
        *root = (Node*)malloc(sizeof(Node));

        (*root)->item = item;
        (*root)->left = (*root)->right = NULL;
    }
    else {
        while (temp != NULL) {
            if (item > temp->item) {
                prev = temp;
                temp = temp->right;
            }
            else {
                prev = temp;
                temp = temp->left;
            }
        }
        temp = (Node*)malloc(sizeof(Node));
        temp->item = item;

        if (item >= prev->item)
            prev->right = temp;
        else
            prev->left = temp;
    }
}

void DFS(Node* root)
{
    if (root) {
        if (root->left)
            DFS(root->left);

        if (root->right)
            DFS(root->right);

        printf("%d  ", root->item);
    }
}

int search(Node* root, int item)
{
    while (root != NULL) {
        if (item > root->item)
            root = root->right;
        else if (item < root->item)
            root = root->left;
        else
            return 1;
    }
    return 0;
}

int main()
{

    struct node* head = NULL;

    AddNode(&head, 10);
    AddNode(&head, 20);
    AddNode(&head, 40);
    AddNode(&head, 30);
    AddNode(&head, 60);

    printf("Tree Items:\n");
    DFS(head);
    printf("\n");

    if (search(head, 70))
        printf("%d item found in tree.\n", 70);
    else
        printf("%d item not found in tree.\n", 70);

    if (search(head, 40))
        printf("%d item found in tree.\n", 40);
    else
        printf("%d item not found in tree.\n", 40);

    return 0;
}

Output:

Tree Items:
30  60  40  20  10  
70 item not found in tree.
40 item found in tree.

Explanation:

Here, we created a self-referential structure to implement a Binary Tree, a function to add a node into the binary tree, and a non-recursive function search() to search given item in the tree.

In the main() function, we created a binary search tree, and called the function search() to search the given item.

ADVERTISEMENT
ADVERTISEMENT


Comments and Discussions!



ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.