Home > Software design >  C Program to Search a Node in Binary Tree
C Program to Search a Node in Binary Tree

Time:07-12

this code is from binary search tree I don't know this code showing same output

I don't know where the problem is occurring I already tried to change the variables but it didn't work What seems to be the problem? i already tried so many things but still not able to fix the errors.

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

****// Basic struct of Tree****
struct node
{
    int data;
    struct node *left;
    struct node *right;
};

****// Function to create a new Node****
struct node *createNode(int item)
{

    struct node *newNode = malloc(sizeof(struct node));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->data = item;
    return newNode;
}
int search(struct node *root, int value)
{
    if (root == NULL)
        return 0;
    if (root->data == value)
        return 1;
    if (root->data < value)
        return search(root->right, value);
    else
        return search(root->left, value);
}

int main()
{
    **// struct node *root = NULL;**
    struct node *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    root->left->right->left = createNode(7);
    root->left->right->right = createNode(8);
    root->right->right->left = createNode(9);

    int item = 34;

    // Function to find item in the tree
    int found = search(root, item);

    if (found)
        printf("%d value is found in the tree", item);
    else
        printf("%d value not found", item);

    return 0;
}

CodePudding user response:

The problem is that your search function expects to get a binary search tree, but your main program created a binary tree that is not a binary search tree, but this:

             1
           /   \
          2     3
         / \     \
        4   5     6
           / \   /
          7   8 9

And of course, a search for 34 will anyway return 0, as it does not occur anywhere in this tree. But even if you would search for let's say 8, it would return 0.

Your search code will not work with such a tree. If you would have made a binary search tree, like for instance this one:

             6
           /   \
          2     7
         / \     \
        1   4     9
           / \   /
          3   5 8

...then it would work when calling search for any value in or not in the tree. For instance, this will print "5 value is found in the tree":

int main()
{
    struct node *root = createNode(6);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(4);
    root->right->right = createNode(9);
    root->left->right->left = createNode(3);
    root->left->right->right = createNode(5);
    root->right->right->left = createNode(8);

    int item = 5;

    // Function to find item in the tree
    int found = search(root, item);

    if (found)
        printf("%d value is found in the tree", item);
    else
        printf("%d value not found", item);

    return 0;
}

CodePudding user response:

This function is for binary search tree (BST).

int search(struct node *root, int value)
{
    if (root == NULL)
        return 0;
    if (root->data == value)
        return 1;
    if (root->data < value)
        return search(root->right, value);
    else
        return search(root->left, value);
}

As you need to a program to work on any binary tree.

You can change it to work on an any binary tree.

int search(struct node *root, int value)
{
    if (root == NULL)
        return 0;
    if (root->data == value)
        return 1;
    return search(root->right, value) || search(root->left, value);
}
  • Related